Research map / Bandits and online learning / RL theory and MDPs

Policy-Regret Minimization in Markov Games with Function Approximation

ICML 2025 · Bandits and online learning › RL theory and MDPs · approach: Regret bounds with function approximation

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 BOVL, a batching-and-optimism value and likelihood fitting algorithm that achieves Õ(√T) policy regret in two-player Markov games with function approximation against memory-bounded stationary adversaries, under ℓ2-type Eluder conditions.

Problem

Policy-regret minimization in Markov games against adaptive, reactive adversaries when state and action spaces are large or continuous, where tabular guarantees do not apply.

Approach

Combines squared-loss value function fitting with log-likelihood adversary modeling under optimism, uses batching so the adversary's response stabilizes, and controls batches with large in-batch error via ℓ2-type Eluder arguments; replaces the consistency assumption with a Lipschitz adversary assumption and controls batches with large total variation loss instead of log-likelihood.

Key results

• BOVL achieves policy regret Õ(V̄(H+m)√(d_E γ T)) for general function classes with ℓ2-type Eluder coefficients, matching the optimal O(√T) rate.
• In the linear case, the bound becomes V̄(m+H)(d_in ∨ d_adv)√((H+B)T), and in the tabular case V̄(m+H)SA√((H+B)^3 T).
• Tabular instantiation improves over APE-OVE (Nguyen-Tang & Arora, 2024a) by a factor of sqrt(HSA/(B d*)), which can be large when the minimum visitation probability d* is small.

Measured effects reported in the paper

Limitations

• Tri-level optimization for optimistic planning generally cannot be solved efficiently; analysis is primarily theoretical.
• Restricted to m-memory bounded and stationary adversaries; unbounded-memory or non-stationary adversaries are infeasible.
• Requires Lipschitzness assumptions on value functions and adversary response, and knowledge of m and a realizable adversary model class.

Experimental setup

Metrics: policy regret

Baselines: APE-OVE (Nguyen-Tang & Arora, 2024a)

Builds on: Nguyen-Tang & Arora (2024a) policy regret in Markov games GOLF Xiong et al. (2023) l2-type Eluder condition Arora et al. (2012b) batching for policy regret Jin et al. (2021) Bellman completeness

Closest papers by meaning

• Learning in Markov Games with Adaptive Adversaries: Policy Regret, Fundamental Barriers, and Efficient Algorithms (NeurIPS 2024 · similarity 0.93)
• Rate-Optimal Policy Optimization for Linear Markov Decision Processes (ICML 2024 · similarity 0.90)
• Best of Both Worlds: Regret Minimization versus Minimax Play (ICML 2025 · similarity 0.89)
• Near-Optimal Reinforcement Learning with Self-Play under Adaptivity Constraints (ICML 2024 · similarity 0.89)
• Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback (ICML 2025 · similarity 0.89)
• Refining Minimax Regret for Unsupervised Environment Design (ICML 2024 · similarity 0.89)