Multi-Agent Learning Under Bandit Feedback

1,526 concepts947 papers3 proposals

In classical game theory and multi-agent reinforcement learning, algorithms often assume that players operate with perfect visibility. When an agent selects an action, they typically receive full-information feedback: they observe not only the reward of their chosen action but also the counterfactual rewards of all the actions they could have taken. Furthermore, they can often directly observe the exact actions or internal strategies of their competitors.

In real-world decentralized systems—such as autonomous traffic routing, high-frequency financial markets, or ad auctions—the lights are effectively turned off. Agents operate under bandit feedback (or payoff-based feedback), meaning they only observe the scalar reward or cost of the specific action they executed. They remain blind to what would have happened had they chosen a different path, and they cannot observe their opponents' moves.

Shifting from full-information to bandit feedback introduces severe mathematical hurdles. However, recent algorithmic breakthroughs demonstrate that decentralized agents can still converge to stable equilibria by leveraging regularization, strategic forgetting, and controlled exploration.

The Obstacles of Blindness: Non-Stationarity and Noise

Why does the lack of counterfactual information break standard learning algorithms? Under full-information feedback, an agent can easily compute the gradient of their reward function or track their cumulative regret across all possible strategies. When you strip this away, two core problems emerge:

  1. The Efficiency Trap: Without counterfactual data, standard no-regret algorithms struggle to evaluate unselected actions. As Jibang Wu et al. demonstrate in Multi-Agent Learning for Iterative Dominance Elimination: Formal Barriers and New Algorithms, this lack of information causes standard learning dynamics to take exponentially long to eliminate iteratively dominated actions, trapping agents in highly inefficient strategies.
  2. Time-Inhomogeneous Noise: In a multi-agent game, every player is updating their strategy simultaneously. Because an agent can only see their own realized rewards, the opponent's unobservable strategy shifts manifest as a highly volatile, non-stationary environment. As noted by Zaiwei Chen et al. in A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Games, this creates complex, time-inhomogeneous noise that invalidates standard Markov chain mixing properties, making it incredibly difficult to estimate the true state transitions or game gradients.

Stabilizing the Path via Regularization

To force independent, blind agents to converge to a stable equilibrium without explicit coordination, researchers inject structural biases into the learning dynamics. The most prominent tool for this is regularization.

Instead of greedily maximizing expected rewards based on noisy point evaluations, agents use regularized learning frameworks like Follow the Regularized Leader (FTRL). For instance, Yang Cai et al. study this in Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedback. By combining entropy regularization with Nash-V value updates, the authors enable agents to achieve last-iterate convergence in Markov games.

The intuition behind why this works lies in how entropy regularization alters the learning landscape:

Greedy Learning (No Regularization)       Entropy-Regularized Learning
   Strategy shifts aggressively              Smooth, cautious updates
   Towards noisy local optima                Maintains wide action support
   Result: Limit cycles / Divergence         Result: Last-iterate convergence

The regularizer penalizes policies that become deterministic too quickly. By forcing the agent to maintain a smoother, more randomized strategy, it ensures that they continue to implicitly sample all actions. This smooths out the volatile gradient estimates caused by the opponent's hidden movements, guiding the system to a Nash equilibrium without requiring any direct communication or opponent observation.

A similar principle is utilized by Maryam Kamgarpour et al. in Learning Nash Equilibria in Monotone Games, where Tikhonov regularization is integrated into a gradient-free approach to stabilize convergence in games where the underlying mathematical structure of the cost functions is entirely unknown.

Strategic Forgetting and Exploration Control

In a pure bandit setting, an agent faces a strict exploration-exploitation trade-off. If they do not explore unchosen paths, they cannot learn; if they explore too much, they destabilize the game for everyone else. Two primary mechanisms balance this dynamic:

Decaying Exploration Factors

In potential games, agents' interests are aligned through a shared global objective. Amélie Héliou et al. show in Learning with Bandit Feedback in Potential Games that if agents use no-regret algorithms (like Exponential Weights) but carefully decrease their explicit exploration factor over time, the actual sequence of play—rather than just the long-term average—reaches a stable Nash equilibrium at a surprisingly rapid rate.

Diminishing Historical Rewards

In full-information settings, keeping a complete, unweighted history of past rewards helps compute accurate averages. In bandit settings, however, old data is toxic: it reflects historical opponent strategies that have long since changed.

To overcome the "efficiency trap" of dominated actions, the Exp3-DH (Diminishing Historical rewards) algorithm, introduced by Jibang Wu et al., strategically discounts past data. By actively "forgetting" the distant past, the algorithm prevents stale feedback from anchoring the agent's current decisions. This allows the player to adapt rapidly to the current strategic reality, collapsing the time required to eliminate dominated actions from exponential to polynomial time.

Which Equilibria Survive Partial Information?

When a learning system is constantly perturbed by the inherent variance of bandit feedback, not all game-theoretic equilibria are equally robust.

Angeliki Giannou et al. explore this boundary in Survival of the strictest: Stable and unstable equilibria under regularized learning with partial information. The authors prove that under regularized learning with partial feedback, only strict Nash equilibria are stable and attracting. Mixed equilibria, where players randomize their strategies and are mathematically indifferent between multiple choices, are fundamentally unstable under bandit feedback; the persistent noise from point evaluations inevitably knocks the players off-balance.

Crucially, however, the authors also demonstrate a surprising "robustness to uncertainty" in The convergence rate of regularized learning in games: From bandits and uncertainty to optimism and beyond. They reveal that the ultimate speed at which players reach a strict Nash equilibrium depends entirely on the geometric properties of their chosen regularizer, rather than whether they have access to full-information counterfactuals or limited bandit feedback. This provides a profound theoretical justification for the field: with the right regularizer, learning under total blindness can be just as asymptotically efficient as learning with perfect vision.

History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_bandit_feedback_constraints_36c0309b,
  title = {bandit feedback constraints},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/bandit-feedback-constraints/rdr_36c0309b221f43a8b706efc6b91152f7},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_bandit_feedback_constraints_36c0309b_v1,
  title = {bandit feedback constraints},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/bandit-feedback-constraints/rdr_36c0309b221f43a8b706efc6b91152f7/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake