Research map / Bandits and online learning / Online convex optimization and games

Learning Imperfect Information Extensive-form Games with Last-iterate Convergence under Bandit Feedback

ICML 2025 · Bandits and online learning › Online convex optimization and games · approach: Last-iterate convergence in games

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes an uncoupled OMD algorithm with a virtual-transition-weighted negentropy regularizer for learning approximate Nash equilibria in two-player zero-sum IIEFGs under bandit feedback, with finite-time last-iterate convergence of order k^{-1/8} (high probability) and k^{-1/6} (expectation).

Problem

Learning approximate Nash equilibria in two-player zero-sum imperfect information extensive-form games from bandit (trajectory-only) feedback with last-iterate rather than average-iterate guarantees.

Approach

Replaces the dilated negentropy regularizer with a negentropy weighted by a designed "virtual transition" over the infoset-action space, chosen to maximize the minimum visitation probability across infosets, so that entropy-regularized OMD with bandit loss estimates has a controlled stability term and a closed-form policy update.

Key results

• Finite-time last-iterate convergence rate of order Õ((X+Y)[(XA+YB)^{1/2}+(X+Y)^{1/4}H] k^{-1/8}) to NE with high probability under bandit feedback.
• In expectation, the NE gap converges at Õ((X+Y)[(X^2A+Y^2B)^{1/2}+(X+Y)^{1/4}H] k^{-1/6}).
• Lower bound Ω(√(XA+YB) k^{-1/2}) for uncoupled bandit last-iterate algorithms, so the upper bound is loose by roughly Õ((X+Y)k^{3/8}).

Measured effects reported in the paper

Limitations

• Upper bound k^{-1/8} is loose compared with the k^{-1/2} lower bound and with O(1/k) full-information rates.
• Virtual transition construction requires knowing the game tree structure a priori, which is impractical for very large games such as no-limit Texas hold'em.
• Rate in expectation is weaker (k^{-1/6}), and the analysis relies on clipping the loss estimator to keep the policy update within a constrained feasible set.

Experimental setup

Datasets: Lewis Signaling Kuhn Poker Leduc Poker Liar's Dice

Benchmarks: Lewis Signaling Kuhn Poker Leduc Poker Liar's Dice

Metrics: NE gap theoretical convergence rate

Baselines: Lewis Signaling baselines Kuhn Poker baselines Leduc Poker baselines Liar's Dice baselines

Builds on: Bai et al. (2022) balanced exploration OMD Fiegel et al. (2023) balanced transitions Lee et al. (2021) dilated negentropy last-iterate Cai et al. (2023) bandit last-iterate matrix games Kozuno et al. (2021) OMD for POMGs

Closest papers by meaning

• A Policy-Gradient Approach to Solving Imperfect-Information Games with Best-Iterate Convergence (ICLR 2025 · similarity 0.93)
• The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback (ICML 2025 · similarity 0.91)
• Local and Adaptive Mirror Descents in Extensive-Form Games (NeurIPS 2024 · similarity 0.91)
• Near-Optimal Last-Iterate Convergence for Zero-Sum Games with Bandit Feedback and Opponent Actions (NeurIPS 2026 · similarity 0.90)
• From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications (NeurIPS 2025 · similarity 0.89)
• No-regret Learning in Harmonic Games: Extrapolation in the Face of Conflicting Interests (NeurIPS 2024 · similarity 0.89)