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.
- Nicolò Cesa-Bianchi, Ofer Dekel, and Ohad Shamir showed in Online Learning with Switching Costs and Other Adaptive Adversaries that even a tiny memory (e.g., $m=2$) makes the learner's job significantly harder, particularly in bandit settings where feedback is limited.
- In more complex scenarios, like Partially Observable Markov Games (POMGs), Raman Arora demonstrates in Minimax-Optimal Policy Regret in Partially Observable Markov Games that as long as the influence of past actions fades over time, we can still achieve optimal learning rates.
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.
- Information Hiding: By staying still, you prevent the adversary from gaining new information about your learning algorithm's internal state.
- 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.