CS Paper Radar

Near-Optimal $\sqrt{K}$-Regret for Online Learning in Uninformed Markov Games

Junyan Liu, Haipeng Luo, Lillian J. Ratliff, Zihan Zhang

cs.LG stat.ML ·submitted 2026-11-01 06:56 UTC · v1

Abstract

We study online learning in two-player uninformed Markov games, where the opponent may follow an arbitrary, unknown policy in each episode and the learner does not observe the opponent's actions. [TWYS21] showed that achieving sublinear external regret requires an exponential dependence on the episode length $H$. Motivated by this limitation, they studied the weaker notion of Nash-value regret and obtained an $\widetilde{O}(K^{2/3})$ regret bound, where $K$ is the number of episodes. More recently, [LLZR26] introduced a stronger notion called empirical Nash-value regret and achieved an $\widetilde{O}(\sqrt{K})$ bound when the opponent's non-stationarity is moderate, including the case where the opponent follows a fixed policy. However, whether the $\sqrt{K}$ rate is achievable in the worst case remained open. In this paper, we resolve this open question by developing an algorithm that achieves $\widetilde{O}(H^{3/2}S\sqrt{AK})$ empirical Nash-value regret against arbitrary opponent policies, where $S$ is the number of states and $A$ is the number of learner's actions. Specifically, our algorithm combines global and local planning by maintaining a collection of candidate predictions of future losses, each associated with a policy. Global planning learns which candidates to favor across episodes, while local planning combines their policies differently at each state to make decisions. A key ingredient is to coordinate these two components to control the discrepancy between local loss estimates and the total loss of the executed policy, using only the learner's observed trajectories.

Closest papers

Nearest neighbours by meaning across the whole index.

Optimal Alternating Regret for Online Learning and Games

cs.LG cs.GTstat.ML ·2026-08-25 ·Yixin Tao, Weiqiang Zheng
theoryhighly cited similarity 0.79
Abstract · 21 pages

We settle the minimax-optimal alternating regret, a regret notion motivated by alternating learning dynamics in games, for both online linear optimization (OLO) and online convex optimization (OCO). For OLO over the probability simplex $Δ_d$, we give an algorithm with $O(\log d)$ alternating regret that remains a constant for any time horizon $T$, and a matching lower bound. Our constant regret bound significantly improves previous results with $O(\log ^{2/3}d \cdot T^{1/3})$ regret [Cevher, Cutkosky, Kavis, Piliouras, Skoulakis, Viano, NeurIPS 2023, Hait, Li, Luo, Zhang, COLT 2025]. As a result, we obtain alternating learning dynamics with $O(\log d /T)$ convergence to Nash equilibria in two-player zero-sum games and $O(\log d /T)$ convergence to coarse correlated equilibria in two-player general-sum games. This is the first uncoupled learning dynamics with $O(1/T)$ convergence to CCE in two-player general-sum games, while all prior works suffer additional $\log T$ factors. For general OCO over a $d$-dimensional compact convex set, we give an algorithm with $O(d\log (1+T/d))$ alternating regret, improving the previous best of $\widetilde{O}(d^{2/3}T^{1/3})$. We also prove a matching lower bound of $Ω(d\log (1+T/d))$, showing that the $Ω(\log T)$ factor is unavoidable.

0.32

Optimistic Hedge in General-Sum Games: Fundamental Limits and Regret Bounds via Temporal Approximation

cs.LG cs.GT ·2026-11-04 ·Yuval Dagan, Nadav Eisen, Liad Erez, Tomer Koren
theory similarity 0.74
Abstract

Optimistic Hedge, a multiplicative weight update with one step of extrapolation, is one of the most natural regret-minimizing dynamics for games, and characterizing its regret has been a longstanding open question. Daskalakis, Fishelson and Golowich proved that if all $m$ players in a finite general-sum game follow Optimistic Hedge with a fixed learning rate, each player's regret is polylogarithmic in the horizon $T$. Subsequently, Ha showed that an appropriate choice of learning rate makes each player's regret bounded independently of $T$. This bound, however, is non-constructive and its dependence on the number of actions $n$ is not explicit, leaving open whether Optimistic Hedge can achieve a constant regret bound which is polynomial in the size of the game. We show that the answer hinges on the number of players. In two-player games, there is a learning rate for which Optimistic Hedge guarantees $O(n\log n)$ regret independent of the horizon. In three-player games, however, no such bound is possible: for any learning rate up to an absolute constant and for sufficiently large horizon $T$, there is a game with $n$ actions per player in which some player's regret is $2^{Ω(n)}$, and more generally, for every $m\ge3$ we construct $m$-player games in which some player's regret is $2^{Ω(mn)}$; for learning rates above $2^{-Ω(mn)}$, that player's regret even grows linearly in $T$. Our upper bound is based on a temporal approximation framework for the analysis of Optimistic Hedge. Starting from the variance-based RVU bound of Daskalakis et al., we approximate the losses over time-localized windows by well-behaved functions, whose total variation is a small fraction of their cumulative variance. In $m$-player games, the same framework gives a significantly simplified proof of the recent $O(\sqrt{m}\log n\log T)$ regret bound due to Ha.

0.16

Minimax Alternating Regret for the Experts Problem and Online Convex Optimization

cs.LG stat.ML ·2026-08-25 ·Mengxiao Zhang
theory similarity 0.74
Abstract

In this paper, we study alternating regret in online convex optimization (OCO), motivated by the success of alternating learning dynamics in two-player games. Although previous works have shown that $o(\sqrt{T})$ alternating regret is achievable under various assumptions on the loss functions and feasible domains, the minimax regret rate has remained open even for the expert problem. In this paper, we resolve this question by showing matching lower and upper bounds for both the expert problem and general OCO. Somewhat surprisingly, for the $d$-expert problem, we show that the minimax alternating regret is $Θ(\log d)$ by providing both a lower bound and an algorithm achieving a matching upper bound. This significantly improves upon the $O(T^{1/3}\log^{2/3} d)$ established by [HLLZ25]. We further extend our results to general OCO over a $d$-dimensional compact convex set and prove that the worst-case minimax alternating regret is $Θ\left(d\log \left(1+\frac{T}{d}\right)\right)$, also significantly improving upon the $O((d\log T)^{2/3}T^{1/3})$ upper bound and resolving the open problem posed by [CCK+23,HLLZ25]. As a direct implication, our alternating dynamics achieve $O(\frac{\log d}{T})$ convergence to Nash equilibrium in two-player zero-sum games, matching the state of the art, and give the first such convergence rate to coarse correlated equilibrium in two-player general-sum games. Technically, our upper bound for the expert problem is achieved by a corrected variant of Hedge. We extend the same corrected-potential argument to continuous action sets to obtain the optimal alternating-regret rate for OCO. For the lower bounds, the construction for the expert problem repeatedly eliminates half of the candidate experts, while the OCO lower bound instance construction replaces this discrete elimination by a more involved multiscale construction on the unit disk.

0.26

High-Probability Nash Regret for Decentralized Learning in Markov $α$-Potential Games: Episodic and Fully Online Asynchronous Algorithms with Applications to Markov Congestion Games

cs.LG cs.GTcs.MAeess.SY+1 ·2026-09-14 ·S. Rasoul Etesami
similarity 0.74
Abstract

We study decentralized learning of Nash equilibria (NE) in infinite-horizon discounted Markov games under bandit feedback, focusing on Markov $α$-potential games. We develop KL-projected natural policy gradient (NPG) algorithms in two settings: an episodic setting with frozen policies during sampling and a fully online setting in which players receive a single realized cost sample per time step and update their policies asynchronously along a continuing trajectory. We establish finite-time high-probability NE regret bounds of order $\widetilde O(T^{-1/4})$ and $\widetilde O(T^{-2/15})$ for the episodic and fully online settings, respectively, up to fixed approximation terms. Crucially, our bounds eliminate the distribution-mismatch coefficient, which can scale prohibitively with the size of the state space, while accommodating potential approximation, estimation-oracle bias, and transition sensitivity. We further identify a state-wise potential structure that yields sharper guarantees with additive dependence on the potential approximation error $α$. We specialize the framework to independent-resource Markov congestion games (IMCGs), establish their approximate-potential and transition-sensitivity properties, and construct decentralized estimation oracles from realized costs. As an application, we introduce strategic online job scheduling on stochastic machines and obtain a scalable decentralized algorithm for learning stable dispatching policies. Overall, our results provide the first finite-time high-probability NE regret guarantees for fully online asynchronous decentralized learning in Markov $α$-potential games, remove distribution-mismatch coefficients from the regret bounds, accommodate fixed estimation-oracle bias, and provide scalable decentralized learning with finite-time guarantees for IMCGs.

0.43

Square-Root Regret for Adversarial Multiplayer Bandits without Collision Information or Shared Randomness

cs.LG cs.MA ·2026-10-05 ·Chenyu Gan
hot direction similarity 0.73
Abstract

We study cooperative multiplayer bandits with adversarial rewards and no collision information. In each of $T$ rounds, each of $m$ labeled players picks one of $K>m$ arms. A player alone on its arm receives that arm's reward in $[0,1]$; players who share an arm receive $0$. Each player observes only its own reward, so it cannot distinguish a collision from an arm with zero reward, and there is neither shared randomness nor a communication channel. Bubeck, Li, Peres and Sellke (2020) obtained regret $\widetilde O(KT^{3/4})$ for two players and $\widetilde O(mK^{3/2}T^{1-1/(2m)})$ for $m$ players, and conjectured that regret $Ω(T^{2/3})$ is unavoidable already for two players. We refute this conjecture. We give a strategy whose expected regret against every oblivious adversary is $O(m^{3/2}\sqrt{KT}\log^2(KmT))$, which is optimal in $K$ and $T$ up to logarithmic factors. Three ideas make this possible. (i) Bits are sent through deliberate collisions as random parity checks, and the regret spent while a message is delayed is charged to the number of arms with positive reward rather than to elapsed time: an adversary that jams the channel with zero rewards forfeits the regret it could inflict. (ii) An exponential-weights learner over sets of arms combines a frequently resampled coordinator arm with a follower assignment that changes only $O(\sqrt{mT/K})$ times in expectation; delayed updates are reconstructed exactly. (iii) We teach the followers a privately chosen row index in a fixed public table using reward observations alone, allowing them to coordinate without shared randomness. The bound holds simultaneously for all reward matrices, even ones chosen with knowledge of the table, and a random table works with probability $1-O(1/(KmT))$.

0.23

Fully Online Decentralized Learning in Stochastic Games with Unknown Independent Chains

cs.LG cs.GTcs.MAeess.SY+1 ·2026-10-01 ·S. Rasoul Etesami
similarity 0.73
Abstract

We consider stochastic games with independent controlled chains and unknown transition kernels, where players observe only their local states and realized payoffs. We develop a fully online, decentralized, and uncoordinated mirror-descent algorithm that operates in the dual space of occupancy measures for approximating stationary Nash equilibrium (NE) policies. The algorithm uses a single transition/reward sample at every primitive time step, relies only on local information, and requires neither coverage of the joint state space nor synchronized episodes. Under uniform-ergodicity and finite-coverage assumptions, we show that, with high probability, the time-averaged fixed-comparator regret decays at the canonical $O(T^{-1/2})$ rate, up to logarithmic factors and polynomial dependence on the game parameters. In particular, the complexity depends on the cover times of the individual local state spaces rather than the product state space, avoiding exponential dependence on the number of players and the sizes of the joint state and action spaces. The resulting finite-time regret bound further yields an approximate coarse-correlated-equilibrium guarantee, which is natural for arbitrary reward functions since computing a stationary $ε$-NE is PPAD-hard in this setting. Under an additional global variational-stability condition, we show that the same fully online algorithm converges asymptotically in the last iterate to a stationary $ε$-NE. Our results provide a fully online and scalable learning framework for stochastic games with unknown independent chains. The algorithm can also be viewed as a primal-dual framework for Markov games that exploits the independence and local structure of the players' controlled transition chains.

0.11

Online Learning with Ordered Experts (via Two-point Feedback)

cs.LG ·2026-11-05 ·Shiliang Zuo
similarity 0.72
Abstract

We study adversarial online learning with expert recommendations in a totally ordered action space, where the experts' recommendations may change and be reordered arbitrarily. Our focus is two-point feedback: on each round the learner plays two current recommendations, observes both, and pays their average. We study two problems. In the separated monotone problem, the loss is the sum of a hidden nondecreasing component and a hidden nonincreasing component, and a query reveals the two components separately. In the BV problem, the losses are bounded and have bounded variation (BV) along the order, and a query reveals only the loss. In the separated monotone problem, two paid observations achieve \[ O\bigl(\log(|\cF|T)\sqrt{T\log|\cF|}\bigr) \] regret against the best of $|\cF|$ experts, within a logarithmic factor of the classical full-information bound. For the BV problem, we obtain $\wtO(\sqrt T+|\cF|)$ regret. We give an application in dynamic pricing with expert advice, showing that two-option menus matches the full information rate up to $\log$ factors. The main technical ingredient is a marginal-preserving endpoint flow estimator. Two observations reveal a loss increment along the order; random paths supply telescoping identities that turn this local information into unbiased loss estimates for all current recommendations. A reversible pair sampler preserves the learner's intended marginal at both played actions. The estimator's second-moment and stability bounds support online updates for both feedback models.

0.17

Nearly Minimax-Optimal Regret for Linear Contextual Bandits with Arbitrary Adaptive Action Sets

cs.LG cs.GT ·2026-09-14 ·Tianyuan Jin
theory similarity 0.72
Abstract

We study stochastic linear contextual bandits with arbitrary action menus that may depend on the fixed parameter and the interaction history. We establish matching upper and lower bounds, up to logarithmic factors. Let $d$ be the dimension, $K$ be the menu size, and $T$ the time horizon. For $2\le K\le d$, we prove an upper bound $\widetilde O(K^{1/4}\sqrt{dT})$. When $T\ge d^2$, we further prove a lower bound $Ω(K^{1/4}\sqrt{dT})$. Thus, for $T\ge d^2$ and $2\le K\le d$, the upper and lower bounds match up to logarithmic factors, and the polynomial dependence on $K$ is optimal. Compared with the previous $\widetilde O(\sqrt{dKT})$ bound, our upper bound improves the dependence on $K$ by a factor of $K^{1/4}$. For $K\ge d$, we prove an upper bound $\widetilde O_{d,T}\left(\sqrt{dT}\min\{\sqrt d,(d\log K)^{1/4}\}\right)$ and a lower bound $Ω\left(\sqrt{dT}\min\left\{\sqrt d,\left(\frac{d\log K}{\log(2d)}\right)^{1/4}\right\}\right)$. Here, $\widetilde O_{d,T}$ omits logarithmic factors only in $d$ and $T$. In particular, for polynomially large $K\ge d$, the upper and lower bounds both scale as $d^{3/4}\sqrt T$ up to logarithmic factors, improving the standard $\widetilde O(d\sqrt T)$ rate by a factor of $d^{1/4}$. As $K$ grows further, the regret smoothly recovers the $d\sqrt T$ scale once $\log K$ reaches order $d$.

0.21