In standard online learning and multi-armed bandit frameworks, an agent's performance is typically evaluated using external regret. External regret answers a simple hindsight question: How much better would I have done if I had chosen the single best action from the start, assuming the environment's sequence of rewards remained exactly the same?
This assumption works perfectly when the environment is static or stochastic. However, it breaks down entirely in reactive environments—such as strategic markets, multi-agent games, or routing networks—where the environment or an adversary changes its future behavior in response to the learner's past actions.
If you change your actions, the adversary changes their strategy, creating a feedback loop. To evaluate performance accurately in these settings, researchers have developed the concept of policy regret.
The Counterfactual Trap of External Regret
To understand why external regret fails against an adaptive adversary, imagine a repeated game of Rock-Paper-Scissors against an opponent who plays a simple adaptive strategy: they always copy your previous move.
If you play a sequence like [Rock, Paper, Scissors, Rock, Paper, Scissors], your opponent plays [Scissors, Rock, Paper, Scissors, Rock, Paper]. You win every single round.
Now let's calculate your external regret in hindsight. If you had instead played a fixed action—say, Rock—every single round, a naive external regret calculation assumes the opponent's actions would remain unchanged ([Scissors, Rock, Paper...]). Under this assumption, playing Rock looks like a decent alternative.
But this is a counterfactual trap. If you had actually committed to playing Rock from the start, your adaptive opponent would have quickly adjusted to play Paper every round, causing you to lose catastrophically.
As Ambuj Tewari et al. argue in Online Bandit Learning against an Adaptive Adversary: from Regret to Policy Regret, external regret is an insufficient metric because it fails to account for how an opponent's future behavior shifts in response to the learner's choices. In fact, Hoda Heidari et al. demonstrate in Tight Policy Regret Bounds for Improving and Decaying Bandits that an algorithm can achieve zero external regret while performing significantly worse than an optimal sequence of actions due to these state-dependent dynamics.
Defining Policy Regret
Policy regret solves this problem by introducing a true counterfactual baseline. Instead of comparing the learner's total loss against a fixed action facing the observed history, policy regret compares the learner's total loss against the loss they would have incurred had they committed to a single fixed policy from the very beginning, accounting for how the adversary would have adapted to that specific policy over time.
Standard Regret:
Learner's Actions: [a_1, a_2, a_3] --> Incurs losses from Env(a_1, a_2, a_3)
Baseline Action: [a*, a*, a* ] --> Naively evaluated against Env(a_1, a_2, a_3)
Policy Regret:
Learner's Actions: [a_1, a_2, a_3] --> Incurs losses from Env(a_1, a_2, a_3)
Baseline Policy: [π, π, π ] --> Evaluated against counterfactual Env(π, π, π)
This metric captures the long-term consequences of an agent's choices. As Raman Arora et al. explain in Policy Regret in Repeated Games, reactive counterfactual regret is essential in strategic settings because it internalizes the feedback loop between the learner's actions and the environment's future states.
This framework is vital across several emerging domains:
- Economic Systems: In multi-agent markets, Nivasini Ananthakrishnan et al. show in Privacy Can Arise Endogenously in an Economic System with Learning Agents that no-policy-regret algorithms are required to model how one agent's strategy alters the incentives and subsequent actions of others.
- Strategic Contracting: When a principal repeatedly hires agents, the agents will actively game the selection process. Natalie Collina et al. utilize policy regret in Repeated Contracting with Multiple Non-Myopic Agents: Policy Regret and Limited Liability to account for how an agent's effort is intrinsically linked to the historical selection policy.
- Evaluating AI Behavior: In Position: Theory of Mind Benchmarks are Broken for Large Language Models, Matthew Riemer et al. highlight that true "functional" theory of mind requires an agent to minimize regret by adapting its actions based on how its opponent will react.
Why Minimizing Policy Regret is Hard
Minimizing policy regret is notoriously difficult because of a fundamental information asymmetry: the learner only observes the rewards along the path they actually chose. They do not observe the counterfactual rewards, nor do they observe how the adversary's internal state would have evolved along a different path.
In Boosting for Control of Dynamical Systems, Naman Agarwal et al. note that a single change in past actions can result in an entirely different trajectory of states, making the calculation of alternative policy performance mathematically intractable without structural constraints.
To quantify this learnability, Kush Bhatia et al. establish a minimax perspective in Online learning with dynamics: A minimax perspective, proving that the feasibility of minimizing policy regret depends heavily on two factors: the sequential complexity of the target policy class and the dynamic stability (or mixing time) of the environment.
Algorithmic Solutions: Breaking the Feedback Loop
To achieve sublinear policy regret, algorithms must find ways to mitigate or "reset" the adversary's memory of past interactions. Two primary mechanisms make this possible.
1. Mini-Batching and Strategic Resets
If an adversary has a bounded memory of $m$ rounds, a learner can decouple its choices from immediate feedback by using a mini-batching wrapper.
The core intuition is simple: the learner selects an action and repeats it continuously for a large block of $T_{block}$ rounds (where $T_{block} \gg m$). During the first $m$ rounds of the block, the adversary is still reacting to the learner's past history. However, for the remaining $T_{block} - m$ rounds, the adversary is forced to settle into a steady-state response to the current action.
This technique allows the learner to treat the reactive environment as a quasi-static system. Ambuj Tewari et al. (Online Bandit Learning against an Adaptive Adversary: from Regret to Policy Regret) and Zongqi Wan et al. (Bounded Memory Adversarial Bandits with Composite Anonymous Delayed Feedback) leverage this exact mechanism to achieve sublinear policy regret bounds against bounded-memory adversaries.
A similar intuition applies to physical environments with state depletion, such as traffic routing or resource allocation. In Congested Bandits: Optimal Routing via Short-term Resets, Pranjal Awasthi et al. demonstrate that algorithms can achieve near-optimal regret by strategically "resetting" congestion—effectively idling or shifting actions to allow congested resources to naturally recover.
2. Controlling Switching Costs
When facing an adaptive adversary, changing actions too frequently is dangerous because it creates a highly unpredictable state trajectory. Consequently, algorithms must penalize frequent changes.
In Online Learning with Switching Costs and Other Adaptive Adversaries, Nicolò Cesa-Bianchi et al. prove that adding switching costs fundamentally alters the hardness of online learning, forcing a worse but optimal $\Theta(T^{2/3})$ regret bound in bandit settings. By explicitly bounding the "price of past mistakes," as explored by Oren Anava et al. in Online Learning for Adversaries with Memory: Price of Past Mistakes, learners can use counterfactual feedback graphs (Raman Arora et al. in Bandits with Feedback Graphs and Switching Costs) to safely explore alternative actions without triggering chaotic adversarial reactions.
Expanding the Benchmark
While early work focused on competing against the best constant action policy, recent literature expands the benchmark to more sophisticated baselines:
- Complete Policy Regret: In environments like tallying bandits, where rewards depend on the frequency of recent plays, competing against a single constant action is a weak baseline. Dhruv Malik et al. provide bounds for complete policy regret in Complete Policy Regret Bounds for Tallying Bandits, evaluating performance against the best optimal sequence of changing actions.
- Contextual Policies: When side information is available, the baseline shifts to competing against the best mapping of contexts to actions. Pier Giuseppe Sessa et al. develop kernel-based methods for this in Contextual Games: Multi-Agent Learning with Side Information.
- History-Dependent Strategies: Odalric Maillard et al. expand the target to the best mapping from history states to actions in Adaptive Bandits: Towards the best history-dependent strategy, providing a rigorous framework for tracking complex, evolving opponents.
Ultimately, by shifting the mathematical target from static hindsight to counterfactual simulation, policy regret provides the theoretical foundation necessary to design algorithms that can safely learn, compete, and stabilize in truly reactive worlds.
Key Foundational Work
Online Bandit Learning against an Adaptive Adversary: from Regret to Policy Regret (2012) — contributed 3 concept elements to this direction.
Adaptive Bandits: Towards the best history-dependent strategy (2011) — contributed 1 concept elements to this direction.
Online Learning of Rested and Restless Bandits (2011) — contributed 1 concept elements to this direction.