Policy Regret for Learning Against Adaptive Adversaries

This direction is merged into another direction: memory-regret phase transition. Its last version stays readable and citable here.

Version 1 of 110 papers22 conceptsfrozen 2026-10-04

In classical online learning, we typically imagine playing against an "oblivious" adversary—a world that picks its moves in advance, regardless of what we do. In this setting, our goal is to minimize external regret: the difference between our total loss and the loss we would have suffered if we had picked the single best action in hindsight.

But real-world environments are rarely oblivious. If you consistently choose a specific route to work, traffic patterns might shift; if you consistently play "Rock" in Roshambo, your opponent will start playing "Paper." When the environment reacts to your actions, external regret becomes a deceptive metric. It asks, "How much better would I have done if I had played Paper every time?" while ignoring the fact that if you had played Paper every time, your opponent would have switched to Scissors.

To solve this, researchers have developed the framework of Policy Regret, focusing on how to learn when the adversary is watching and reacting to your history.

The Counterfactual Trap

The fundamental problem with adaptive adversaries is the "counterfactual" nature of the rewards. As Ambuj Tewari, Ofer Dekel, and Raman Arora argue in Online Bandit Learning against an Adaptive Adversary: from Regret to Policy Regret, standard regret fails because it compares your sequence of actions against a fixed action in a vacuum.

Policy Regret fixes this by comparing your performance against the best policy from a class of policies. Crucially, it evaluates that policy by asking what the adversary would have done if you had followed that policy from the very first step. This accounts for the adversary's ability to learn and adapt to your behavior.

The Bounded Memory Assumption

If an adversary has an infinite memory of everything you have ever done, learning is impossible. Ambuj Tewari and colleagues proved that an adversary with perfect recall can implement "permanent punishments"—if you ever deviate from a path they prefer, they can punish you for the rest of time, making it impossible to achieve sublinear regret.

To make the problem tractable, the field relies on the Bounded Memory principle. This assumes the adversary’s current strategy is only a function of the last $m$ actions you took.

Beating the Adversary by Staying Still

How do you minimize regret against someone who is trying to predict your next move? The most effective strategy is often to slow down.

The recurring mechanism across this research is mini-batching (or epoch-based learning). Instead of changing your action every round, you commit to an action for a block of $L$ rounds.

  1. Information Hiding: By staying still, you prevent the adversary from gaining new information about your learning algorithm's internal state.
  2. Memory Flushing: If the block length $L$ is much larger than the adversary's memory $m$, the adversary's strategy will "settle" into a response for that specific action. The "cost" of their memory only affects the first $m$ rounds of the block; the remaining $L-m$ rounds provide clean data on how that action performs against the adversary's settled response.

Zongqi Wan and Xiaoming Sun applied this logic to even harder settings in Bounded Memory Adversarial Bandits with Composite Anonymous Delayed Feedback, showing that mini-batching can overcome both an adaptive adversary and delayed feedback simultaneously.

From Theory to Gameplay

This tension between learner and adversary isn't just theoretical; it's a core mechanic in "AI-based games." In AI-based Games: Contrabot and What Did You Do?, Michael Cook and Adam M. Smith describe games where players must intentionally vary their patterns to avoid being predicted by an agent's generalization algorithms. This mirrors the theoretical necessity of "out-patterning" an adversary's memory window to maintain an advantage.

By framing the environment as a reactive agent with a finite memory, researchers like Raman Arora and Mehryar Mohri have moved online learning from static optimization toward a robust theory of interaction in repeated games. The key to winning isn't just picking the best move—it's understanding how your moves today shape the world you'll have to play in tomorrow.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_policy_regret_for_learning_against_adapt_47ef2bfe,
  title = {Policy Regret for Learning Against Adaptive Adversaries},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/policy-regret-for-learning-against-adaptive-adversaries/rdr_47ef2bfe63da49e08f5595add258f3b1},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_policy_regret_for_learning_against_adapt_47ef2bfe_v1,
  title = {Policy Regret for Learning Against Adaptive Adversaries},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/policy-regret-for-learning-against-adaptive-adversaries/rdr_47ef2bfe63da49e08f5595add258f3b1/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}