Dual Confidence Bounds for Competitive Reinforcement Learning

48 concepts38 papers1 proposal

In single-agent reinforcement learning, managing uncertainty is well-understood. To explore efficiently, an agent adopts Optimism in the Face of Uncertainty (OFU), adding an exploration bonus to poorly understood states to incentivize discovery. Conversely, to learn safely from offline datasets without making catastrophic mistakes, the agent adopts Pessimism, penalizing uncertainty to avoid poorly sampled regions.

However, when we transition to competitive multi-agent environments—such as two-player zero-sum Markov games—this single-sided approach breaks down. If a maximizing agent is unilaterally optimistic, it assumes the environment will yield high rewards. But in a game, the "environment" includes a strategic opponent actively minimizing those rewards. An overly optimistic agent might walk into a trap, while an overly pessimistic agent might concede winning positions unnecessarily.

To resolve this, a powerful paradigm has emerged: dual confidence bounds (or dual-sided value estimation). Instead of maintaining a single uncertainty-adjusted value function, algorithms maintain simultaneous upper and lower bounds tailored to the strategic objectives of both players.

Online Exploration: Dual-Sided Optimism

When exploring an unknown game, how do we incentivize agents to find the true Nash Equilibrium? If we only incentivize one player to explore, the game becomes strategically unbalanced.

As shown by Yu Bai et al. and Qiaomin Xie et al., efficient exploration requires maintaining separate upper and lower confidence bounds for the value functions of competing agents:

  • The maximizing player evaluates actions using an upper confidence bound (UCB), remaining optimistic about its potential payoffs.
  • The minimizing player evaluates actions using a lower confidence bound (LCB), remaining optimistic about its ability to minimize the payoff (which means assuming a lower value).

By solving for the Nash Equilibrium of the surrogate game defined by these joint optimistic and pessimistic estimates, the system ensures that agents are driven toward states where their collective knowledge is weakest. Yu Bai et al. demonstrated that this dual-bound approach allows self-play algorithms to achieve near-optimal sample complexity, making learning a Nash Equilibrium nearly as efficient as single-agent learning.

Similarly, Dongruo Zhou et al. utilized this dual-sided optimism to achieve minimax optimal regret in linear mixture Markov games, proving that selecting the most optimistic model for the max-player and the most pessimistic model for the min-player from a confidence set prevents agents from getting stuck in strategically irrelevant subgames.

Offline Learning: Dual-Sided Pessimism

The problem flips completely when we cannot interact with the environment and must learn strictly from a static offline dataset. Here, the primary threat is distribution shift: if an agent chooses an action not well-represented in the dataset, the value estimate could be wildly inaccurate.

In single-agent offline RL, we simply penalize unvisited states. But in a zero-sum game, if we only penalize the maximizing player, the minimizing player will exploit this artificial asymmetry during policy optimization.

To counter this, Han Zhong et al. and Qiwen Cui et al. introduced dual-sided pessimism (or double-sided pessimism). Under this framework:

  • The maximizing player utilizes a conservative lower bound on rewards to avoid over-optimism about poorly sampled actions.
  • The minimizing player utilizes a conservative upper bound on rewards, preventing it from underestimating potential losses in poorly explored regions.

By subtracting an uncertainty bonus for the max-player and adding it for the min-player, the algorithm constrains the estimated value of the game from both directions. This dual-sided squeeze ensures that the computed equilibrium is robust against distribution shifts and does not rely on high-reward outliers unsupported by data.

Why It Works: The Saddle-Point Squeeze

To build intuition for why dual bounding works, consider a classic matrix game where the payoffs are partially known. If we represent the uncertainty of each state-action pair as an interval $[L, U]$, a standard single-agent algorithm might just take the midpoint or an optimistic upper bound.

However, as Jilles Dibangoye et al. demonstrate in heuristic search value iteration, tracking both $U$ and $L$ allows the algorithm to capture the opposing objectives directly. This concept traces back to search algorithms like the simultaneous-move alpha-beta pruning developed by Abdallah Saffidine, which maintains a range of possible payoffs defined by pessimistic and optimistic bounds to prune dominated actions without computing exact Nash values.

When alternating updates—such as the alternating optimistic-pessimistic estimation proposed by Baihe Huang et al.—the gap between $U$ and $L$ acts as a direct measure of game-theoretic uncertainty. When computing a Nash equilibrium on these bounds, the max-player plays against the LCB of the min-player's strategy, and the min-player plays against the UCB of the max-player's strategy. This forces the equilibrium strategy to either exploit a known vulnerability or guide the system into an uncertain state that collapses the $[L, U]$ gap, effectively squeezing the surrogate game until it converges to the true saddle point.

Extension to Partial Information and Asymmetric Games

The principle of dual confidence balancing extends far beyond symmetric zero-sum Markov games.

For instance, in games with bandit feedback where the payoff matrix is entirely hidden and only noisy samples are observed, Brendan O'Donoghue et al. show that maintaining a deterministic upper confidence bound across the matrix prevents an informed opponent from exploiting temporary strategic weaknesses. In the same vein, Shinji Ito et al. combine optimism under uncertainty with safety-first maximin estimation to achieve logarithmic regret against arbitrary opponents.

Even in hierarchical settings like Stackelberg games, where a leader commits to a strategy before a follower responds, dual bounding plays a vital role. Han Zhong et al. demonstrated that adapting least-squares value iteration to incorporate online optimism and offline pessimism allows leaders to efficiently find Stackelberg-Nash equilibria even when facing myopically rational followers with unknown utilities.

Key Foundational Work

Online Multiagent Learning against Memory Bounded Adversaries (2008) — contributed 1 concept elements to this direction.
Algorithms for Finding Approximate Formations in Games (2010) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_dual_sided_pessimism_48793840,
  title = {dual-sided pessimism},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/dual-sided-pessimism/rdr_4879384072a048ccb36f7a3cc7c3a9db},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_dual_sided_pessimism_48793840_v1,
  title = {dual-sided pessimism},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/dual-sided-pessimism/rdr_4879384072a048ccb36f7a3cc7c3a9db/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake