Policy Regret for Adaptive Online Learning

This direction is split into other directions: policy regret. Its last version stays readable and citable here.

Version 1 of 138 papers56 conceptsfrozen 2026-10-04

In classical online learning, we often treat the environment as a static "black box." We assume that if we had chosen a different action in the past, the environment’s future behavior would remain unchanged. This assumption allows us to use external regret—the difference between our actual rewards and the rewards of the best fixed action in hindsight.

However, in the real world, environments are rarely oblivious. Whether in high-frequency trading, autonomous driving, or multi-agent games, the "environment" is often another intelligent agent that learns and reacts to our choices. If you change your strategy, they change theirs. In these reactive settings, external regret becomes a flawed metric because it fails to account for the counterfactual: how the adversary would have adapted if we had played differently.

The Counterfactual Gap

The fundamental problem with standard regret is that it compares the learner's performance against a sequence of rewards that was generated by the actual history of play. As Ambuj Tewari, Ofer Dekel, and Raman Arora argue in Online Bandit Learning against an Adaptive Adversary: from Regret to Policy Regret, this ignores the long-term consequences of a policy.

To fix this, researchers use policy regret. Instead of comparing yourself to the best action given what did happen, policy regret compares your total reward to the reward you would have received if you had committed to a single fixed policy from the very beginning. This "counterfactual" approach forces the metric to account for the adversary’s eventual adaptation to that specific, consistent policy.

Learning in Environments with Memory

When an adversary has "memory," your current action influences their future state. Elad Hazan, Oren Anava, and Shie Mannor demonstrate in Online Learning for Loss Functions with Memory and Applications to Statistical Arbitrage that conventional metrics cannot capture these path-dependent realities.

If an adversary remembers the last $m$ rounds, a single change in your action can ripple through the next $m$ steps of the adversary's strategy. Policy regret captures this by evaluating the learner against the best fixed sequence of actions while explicitly accounting for how the adversary's memory would have evolved under that sequence. To achieve sublinear policy regret in these settings, algorithms often use "mini-batching"—playing the same action for a block of time to let the adversary's memory stabilize before switching.

From Static Arms to Dynamic Sequences

In many modern bandit problems, the "best" strategy isn't to stick to one arm, but to follow a specific sequence. This is most evident in "rotting" or "congested" environments:

  • Rotting Bandits: As explored by Nir Levine and Koby Crammer in Rotting Bandits, the reward of an arm decreases every time you pull it. Here, the optimal policy is a sequence: use the best arm until it "rots" below the value of the second-best, then switch.
  • Tallying Bandits: In Complete Policy Regret Bounds for Tallying Bandits, Dhruv Malik and colleagues show that when rewards depend on how often an action was played recently, the learner must compete with the best possible sequence of actions, not just the best single action.
  • Congested Bandits: Pranjal Awasthi and Kush Bhatia describe in Congested Bandits: Optimal Routing via Short-term Resets how resources (like roads) need "rest" to recover their utility. Policy regret here measures how well an algorithm manages these recovery cycles compared to an optimal scheduling policy.

Policy Regret in Games and Continual RL

The challenge of policy regret scales up significantly in multi-agent reinforcement learning. In Learning in Markov Games with Adaptive Adversaries: Policy Regret, Fundamental Barriers, and Efficient Algorithms, Raman Arora and Thanh Nguyen-Tang highlight that in Markov Games, the environment's state transition is itself a function of the joint actions.

This perspective is also reshaping how we think about lifelong learning. Michael Bowling and Martha White argue in Rethinking the Foundations for Continual Reinforcement Learning that traditional RL metrics are incompatible with agents that must adapt indefinitely. They propose "deviation regret"—a variation of policy regret—to diagnose whether an agent failed to adopt a better policy that was already within its representational capacity, given the specific history it encountered.

By shifting the benchmark from "what was the best action for the world I saw" to "what was the best policy for the world I would have created," policy regret provides a mathematically rigorous way to design agents that can truly navigate interactive and evolving systems.

Papers in this version

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_policy_regret_for_adaptive_online_learni_0a71cbb3,
  title = {Policy Regret for Adaptive Online Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/policy-regret-for-adaptive-online-learning/rdr_0a71cbb3c87b49e1a63e0de1c503ace4},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_policy_regret_for_adaptive_online_learni_0a71cbb3_v1,
  title = {Policy Regret for Adaptive Online Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/policy-regret-for-adaptive-online-learning/rdr_0a71cbb3c87b49e1a63e0de1c503ace4/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}