Pith. sign in

REVIEW 3 major objections 4 minor 1 cited by

Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games

T0 review · 3 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper introduces VMG, a model-based algorithm that replaces uncertainty bonuses with value-incentivized model fitting and proves near-optimal regret for online Markov games.

desk verdict First bonus-free, value-incentivized algorithm with near-optimal regret for general-sum Markov games under linear mixture models; the regret proofs hold conditional on exact equilibrium and model-optimization oracles. read the letter →

arxiv 2502.09780 v1 pith:W76G6GIW submitted 2025-02-13 cs.LG cs.AIcs.GTmath.OC

Tong Yang , Bo Dai , Lin Xiao , Yuejie Chi This is my paper
classification cs.LGcs.AIcs.GTmath.OC
keywords multi-agentreinforcementlearningMarkovgamescoarsecorrelatedequilibriumNashvalue-incentivizedexplorationreward-biasedmaximumlikelihoodestimationlinearmixturemodelregretminimization
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper proposes VMG, a model-based algorithm for online Markov games that replaces explicit uncertainty bonuses with a value-incentivized regularization of the model estimate. The central claim is that biasing the fitted transition or payoff model toward parameters that raise each player's best-response value, holding the others' policies fixed, yields provably near-optimal exploration. Under a linear mixture model of transitions, VMG attains $\tilde{O}(d\sqrt{H^3T})$ regret for finding coarse correlated equilibria (CCE) of $N$-player general-sum Markov games, and $\tilde{O}(d\sqrt{T})$ regret for two-player zero-sum matrix games, matching up to logarithmic factors the guarantees of UCB-based methods that construct confidence sets. If correct, this gives the first value-incentivized, bonus-free algorithm with near-optimal rates for general-sum games, while permitting simultaneous and uncoupled policy updates.

What carries the argument

The load-bearing object is the value-incentivized regularized estimator: in the Markov game, $f_t = \arg\min_{f\in\mathcal{F}} L_t(f) - \alpha \sum_{n=1}^N V^{\star,\pi^{-n}_t}_{f,n}(\rho)$, where $L_t$ is the negative log-likelihood of collected transitions and $V^{\star,\pi^{-n}}_{f,n}$ is the best-response value of player $n$ under model $f$ when the other players execute $\pi^{-n}_t$. This single regularizer replaces confidence sets: it favors models with larger collective deviation gains, thereby guiding data collection. The proof pairs it with an exact-equilibrium step and a regret decomposition in which the equilibrium of $M_{f_{t-1}}$ makes one term non-positive, while Freedman's inequality and the elliptical-potential lemma bound the cumulative discrepancy between fitted and true models. For KL-regularized games, the best-response policies and the regularizer have closed-form softmax and LogSumExp expressions, making both subproblems tractable first-order computations.

What would settle it

Run VMG on a small linear-mixture two-player zero-sum Markov game while replacing the exact equilibrium oracle with an approximate solver of known duality gap, say 0.05, and track the term $V^{\tilde{\pi}_t,\pi^{-n}}_{f_{t-1}}(\rho) - V^{\pi_t}_{f_{t-1}}(\rho)$ that the proof asserts is non-positive; if it is positive and its cumulative sum grows linearly in $T$, the regret bound $\tilde{O}(d\sqrt{H^3T})$ will be violated and the exact-solver premise is load-bearing.

Watch

Extended reading notes

Core claim

On the paper's own terms, the discovery is that exploration can be incentivized by regularization rather than by optimism: at each round $t$, VMG first computes an equilibrium $\pi_t$ of the current model $M_{f_{t-1}}$, then fits a new model $f_t$ by minimizing the empirical negative log-likelihood minus $\alpha \sum_{n=1}^N V^{\star,\pi^{-n}_t}_{f,n}(\rho)$, the sum of each player's best-response value under the current opponents' policies. The fitted model is therefore tilted toward scenarios in which unilateral deviation is valuable, which steers sampling into informative regions. The proof's key cancellation is that the regret decomposes into a model-shift term, two value-difference terms, and a term involving the previous model; the equilibrium property makes one of these terms non-positive, and maximum-likelihood concentration plus an elliptical-potential argument bounds the rest. Theorem 2 states the resulting bound $\mathrm{Regret}(T) \le \tilde{O}(d\sqrt{H^3T})$ for finding CCEs of general-sum Markov games, and Theorem 1 states the matrix-game analog $\tilde{O}(d\sqrt{T})$. The paper also notes reductions to symmetric games, bandits, and single-agent MDPs, recovering reward-biased maximum likelihood estimation and producing a new regularizer, $V^{\star}_f - V^{\pi_t}_f$, that adds friction against the current policy.

Load-bearing premise

The guarantee rests on the assumption that, each round, Algorithm 2 can solve the equilibrium of the current estimated game (line 4) and the regularized maximum-likelihood problem (line 5) exactly; with approximate solvers, the non-positive term in the regret decomposition is no longer guaranteed to vanish, and the paper proves no error tolerance for either subroutine.

Editorial extensions

If this is right

  • For two-player zero-sum matrix games, VMG's $\tilde{O}(d\sqrt{T})$ regret matches the linear-bandit lower bound up to logarithmic factors, so no bonus-based method can be asymptotically better in the feature dimension $d$.
  • For $N$-player general-sum episodic Markov games with linear mixture transitions, VMG finds an $\varepsilon$-CCE in $\tilde{O}(N d^2 H^3 / \varepsilon^2)$ trajectories, equivalently $\tilde{O}(N d^2 H^4 / \varepsilon^2)$ samples, which is near-optimal up to a factor of $H$ against the minimax sample complexity.
  • The same guarantee covers two-player zero-sum Markov games, where the output is an $\varepsilon$-Nash equilibrium, and the infinite-horizon extension achieves $\tilde{O}(N d^2 / ((1-\gamma)^4 \varepsilon^2))$ sample complexity for $\varepsilon$-optimality.
  • VMG requires no uncertainty sets or bonus construction, and the players update simultaneously and independently, so the approach scales better with the number of agents than asymmetric or coordinated exploration schemes.
  • Because $\min_{t\in[T]} \mathrm{Gap}(\pi_t) \le \mathrm{Regret}(T)/T$, the regret bound directly translates into a PAC-style sample complexity for equilibrium finding.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • An implied but unproven extension is that the same value-incentivized estimator could be paired with nonlinear function classes such as neural networks: the algorithm never constructs bonuses, but the proof's concentration bounds rely on the linear-mixture structure, so the $\tilde{O}(d\sqrt{H^3T})$ rate should not be expected to transfer automatically.
  • The exact-solver requirement suggests a robustness test: if the inner equilibrium solver returns a policy within duality gap $\varepsilon_{\mathrm{in}}$, the regret's additional term may scale roughly like $T \cdot \varepsilon_{\mathrm{in}}$; characterizing this trade-off would turn VMG into a practical algorithm for large games where exact equilibrium computation is infeasible.
  • The bandit and single-agent MDP reductions expose a new regularizer, $V^{\star}_f - V^{\pi_t}_f$, that adds friction against the current policy; one could test in sparse-reward single-agent RL whether this friction term improves exploration over the plain $V^{\star}_f$ bias.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper introduces VMG, a model-based algorithm for online multi-agent reinforcement learning that incentivizes exploration by adding value-based regularizers to the model-estimation objective instead of constructing explicit confidence bonuses. For two-player zero-sum matrix games it claims regret O~(d sqrt(T)) under linear payoff approximation, and for N-player general-sum Markov games with linear mixture transitions it claims regret O~(d sqrt(H^3 T)) for finding CCEs (and NEs in the zero-sum case), with corresponding sample-complexity statements. The proofs decompose the regret, use the regularizer to cancel quadratic error terms, and control the remainder with Hellinger/Freedman concentration and self-normalized inequalities. An infinite-horizon extension is also provided.

Significance. The regret decomposition is coherent, and the cancellation mechanism between the value-incentivized model update and the best-response data-collection policies is elegant. If the oracle assumptions are made explicit and justified, the result would be a meaningful advance: it is, to my knowledge, the first value-incentivized (bonus-free) exploration guarantee for CCEs in general-sum Markov games under linear function approximation, and it permits simultaneous, uncoupled policy updates. The proof also gives a clean template for transferring reward-biased MLE ideas from bandits and single-agent RL to games. The main weakness is that the central guarantee is stated for exact equilibrium computation and exact global solution of a nonconvex regularized MLE, and the paper does not discuss approximate solvers.

major comments (3)
  1. [§3.3, Eq. (76)] The proof of Theorem 2 relies essentially on the assumption that the policy π_t returned by Algorithm 2, line 4 is an exact CCE or NE of the estimated game M_{f_{t-1}}. In Eq. (76), the term involving V^{~π_{t,n}}_{f_{t-1},n}(ρ)−V^{π_t}_{f_{t-1},n}(ρ) is discarded precisely because π_t is an exact equilibrium. If Equilibrium(M_f) returns only an ε-equilibrium, this term contributes an additive Tε error, and the paper gives no sensitivity analysis. Since the theorem states no explicit equilibrium-computation oracle, the claimed Regret(T) bound currently holds only under an unstated exact-solver assumption; this should be stated formally and, ideally, accompanied by a perturbation analysis for approximate equilibria.
  2. [§2.2 Eq. (7) and §3.2 Eq. (22)] Both model-update steps require global minimization of a nonconvex objective. In Eq. (22), the negative log-likelihood is convex, but subtracting α times the sum of best-response value functions V^{⋆,π^{−n}_t}_{f,n}(ρ) breaks convexity in general; in Eq. (7), the closed-form expression in Eq. (9) is available only for β>0, while Theorem 1 states the result for any β≥0. The proof uses the exact optimality of f_t in Eqs. (38) and (77), so an approximate optimizer would introduce an uncontrolled error with no bound in the current analysis. The paper should either state an explicit global-optimization oracle and discuss its cost, or provide a tractable optimization procedure with a convergence guarantee.
  3. [Abstract and §1.1] The phrase 'provably efficient' overstates the current end-to-end guarantee, because the theorem abstracts away both exact equilibrium solving and global regularized-MLE solving. The authors should qualify the claim, for example by saying the result is a statistical regret bound under exact optimization oracles, and should make this caveat visible in the contribution statement rather than only in the proof.
minor comments (4)
  1. [Appendix C.3.2, Lemma 11] The statement of Lemma 11 defines dγ(λ) := 2d log(1 + T/(dλ)), but Eq. (169) in its proof uses dγ(λ) := 2d log(1 + T/((1−γ)^2 λ)). These definitions are inconsistent and should be reconciled.
  2. [Appendix C, Theorem 3] Theorem 3 states that 'the regret of Algorithm 2' satisfies the bound, but the infinite-horizon setting uses Algorithm 6; the theorem statement should refer to Algorithm 6.
  3. [Abstract and §C.2] The abstract reports an infinite-horizon sample complexity of O~(N d^2 /((1−γ)^4 ε^2)), while §C.2 reports O~(γ^2 N d^2 /((1−γ)^4 ε^2)). The γ^2 factor should be included in both places, or the inconsistency should be explained.
  4. [§2.3 and Appendix B.2, Eq. (92)] The typesetting of the regularization coefficient α in Eqs. (12) and (92) is difficult to parse; adding explicit parentheses around the T factor and the logarithmic terms would improve readability.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the value-incentivized regularizer is deliberately matched to the regret proxy, but the regret bounds are proved via concentration and self-normalized inequalities.

full rationale

The central derivation is self-contained. VMG's model update (Eq. 22) regularizes the negative log-likelihood by the sum of best-response values, which mirrors the gap appearing in the regret definition (Eq. 19). This alignment is deliberate, but the proof does not assume the regret bound: Theorem 2 follows from the optimality of the regularized MLE update (Eq. 77), martingale concentration (Lemma 8), and self-normalized value-difference bounds (Lemma 9). The analogous matrix-game proof (Theorem 1) uses the optimality of the regularized least-squares update (Eq. 38) and an elliptical-potential argument (Lemma 7). No fitted parameter is renamed as a prediction; the regularization coefficient is set from T, d, H, and delta, and the bounds are proved rather than assumed. Self-citations, including Cen et al. 2024 and the use of Lemmas from Liu et al. 2024, are contextual or technical and are not load-bearing for the main claims. The exactness of the equilibrium computation and global model update (Algorithm 2, lines 4-5) is an oracle/solvability assumption; if only approximate solvers are available, the non-positive terms in the regret decomposition would acquire uncontrolled error, but this is an implementation gap and correctness risk, not a circular reduction of the theorem to its inputs.

Assumptions & free parameters 1 free parameters · 8 assumptions · 0 invented entities

The central claim rests on the linear function approximation assumptions (payoff linearity for matrix games, linear mixture for transitions), realizability, sub-Gaussian noise, and an exact equilibrium or solver oracle. No new physical or mathematical entities are introduced. The only hand-tuned algorithmic parameter is alpha.

free parameters (1)
  • regularization coefficient alpha = O(sqrt(T/d)) with log factors, exact formulas in Eq. (12), (92), and (146)
    Chosen analytically to balance the regret bound; not fitted to data, but the guarantees depend on this hand-set value.
assumptions (8)
  • domain assumption Assumption 1 (matrix game): payoff matrix is A_omega(i,j)=phi(i,j)^T omega with known features ||phi(i,j)||_2 <= 1 and ||omega||_2 <= sqrt(d).
    Needed for linear regression and self-normalized concentration in Theorem 1; not verified from data.
  • domain assumption Assumption 2 (realizability): true payoff A equals A_omega_star for some omega_star in Omega.
    Without this, the least-squares fit is biased and the regret bound fails.
  • domain assumption Assumption 3: noise in the payoff oracle is i.i.d. zero-mean sub-Gaussian with parameter sigma.
    Used for concentration and Freedman inequalities in Lemma 6.
  • domain assumption Assumption 4 (linear mixture transition model): P_h(s'|s,a)=phi_h(s,a,s')^T theta_h with known feature kernels phi_i in Delta(S), bounded norms.
    Enables self-normalized bounds in Lemma 9 and Theorem 2; a strong structural assumption.
  • domain assumption Assumption 5 (realizability of transition kernel): P equals P_f_star for some f_star in F.
    Needed so MLE concentration is around the true kernel.
  • domain assumption Reward functions are fixed, deterministic, bounded in [0,1] and known; only transitions are learned.
    The algorithm and proof ignore reward learning, a restriction stated in Section 3.2.
  • domain assumption Exact equilibrium oracle and exact regularized MLE solver at every iteration.
    Algorithm 2 lines 4-5; no approximation-error analysis; nonconvex objective makes exact solvability nontrivial.
  • standard math Background concentration facts: Freedman's inequality, matrix determinant lemma, covering numbers, martingale exponential inequality.
    Used as Lemmas 1-5 with citations to Abbasi-Yadkori et al. 2011, Liu et al. 2024, Du et al. 2021, and Jin et al. 2020.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games." pith.science (2026). https://pith.science/paper/W76G6GIW

@misc{pith2026250209780,
  author       = {Pith},
  title        = {Pith review of: Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/W76G6GIW}},
  note         = {Machine review of arXiv:2502.09780}
}
read the original abstract

Multi-agent reinforcement learning (MARL) lies at the heart of a plethora of applications involving the interaction of a group of agents in a shared unknown environment. A prominent framework for studying MARL is Markov games, with the goal of finding various notions of equilibria in a sample-efficient manner, such as the Nash equilibrium (NE) and the coarse correlated equilibrium (CCE). However, existing sample-efficient approaches either require tailored uncertainty estimation under function approximation, or careful coordination of the players. In this paper, we propose a novel model-based algorithm, called VMG, that incentivizes exploration via biasing the empirical estimate of the model parameters towards those with a higher collective best-response values of all the players when fixing the other players' policies, thus encouraging the policy to deviate from its current equilibrium for more exploration. VMG is oblivious to different forms of function approximation, and permits simultaneous and uncoupled policy updates of all players. Theoretically, we also establish that VMG achieves a near-optimal regret for finding both the NEs of two-player zero-sum Markov games and CCEs of multi-player general-sum Markov games under linear function approximation in an online environment, which nearly match their counterparts with sophisticated uncertainty quantification.

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Exploration from a Primal-Dual Lens: Value-Incentivized Actor-Critic Methods for Sample-Efficient Online RL

    cs.LG 2025-06 conditional novelty 6.0 of 10

    VAC is a new actor-critic method with a single optimistic objective and a provably near-optimal regret bound in linear Markov decision processes.

Reference graph

Works this paper leans on

64 extracted references · 43 canonical work pages · cited by 1 Pith paper

  1. [1]

    , " * write output.state after.block = add.period write newline

    ") INTEGERS output.state before.all mid.sentence after.sentence after.block FUNCTION init.state.consts #0 'before.all := #1 'mid.sentence := #2 'after.sentence := #3 'after.block := STRINGS s t FUNCTION output.nonnull 's := output.state mid.sentence = ", " * write output.state after.block = add.period write newline " " write output.state before.all = 'wri...

  2. [2]

    write newline

    " write newline "" before.all 'output.state := FUNCTION fin.entry add.period write newline FUNCTION new.block output.state before.all = 'skip after.block 'output.state := if FUNCTION new.sentence output.state after.block = 'skip output.state before.all = 'skip after.sentence 'output.state := if if FUNCTION not #0 #1 if FUNCTION and 'skip pop #0 if FUNCTIO...

  3. [3]

    Abbasi-Yadkori, D

    Y. Abbasi-Yadkori, D. P \'a l, and C. Szepesv \'a ri. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011

    2011

  4. [4]

    Agarwal, Y

    A. Agarwal, Y. Jin, and T. Zhang. Vo q l: Towards optimal regret in model-free RL with nonlinear function approximation. In The Thirty Sixth Annual Conference on Learning Theory, pages 987--1063. PMLR, 2023

    work page 2023

  5. [5]

    R. J. Aumann. Correlated equilibrium as an expression of bayesian rationality. Econometrica: Journal of the Econometric Society, pages 1--18, 1987

    work page 1987

  6. [6]

    Ayoub, Z

    A. Ayoub, Z. Jia, C. Szepesvari, M. Wang, and L. Yang. Model-based reinforcement learning with value-targeted regression. In International Conference on Machine Learning, pages 463--474. PMLR, 2020

    2020

  7. [7]

    Y. Bai, C. Jin, H. Wang, and C. Xiong. Sample-efficient learning of stackelberg equilibria in general-sum games. Advances in Neural Information Processing Systems, 34: 0 25799--25811, 2021

    work page 2021

  8. [8]

    Bouneffouf

    D. Bouneffouf. Finite-time analysis of the multi-armed bandit problem with known trend. In 2016 IEEE Congress on Evolutionary Computation (CEC), pages 2543--2549. IEEE, 2016

    work page 2016

Show all 64 references
  1. [9]

    Busoniu, R

    L. Busoniu, R. Babuska, and B. De Schutter. A comprehensive survey of multiagent reinforcement learning. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 38 0 (2): 0 156--172, 2008

    2008

  2. [10]

    Q. Cai, Z. Yang, C. Jin, and Z. Wang. Provably efficient exploration in policy optimization. In International Conference on Machine Learning, pages 1283--1294. PMLR, 2020

    2020

  3. [11]

    Y. Cai, H. Luo, C.-Y. Wei, and W. Zheng. Near-optimal policy optimization for correlated equilibrium in general-sum M arkov games. In International Conference on Artificial Intelligence and Statistics, pages 3889--3897. PMLR, 2024

    2024

  4. [12]

    S. Cen, Y. Wei, and Y. Chi. Fast policy extragradient methods for competitive games with entropy regularization. Advances in Neural Information Processing Systems, 34: 0 27952--27964, 2021

    2021

  5. [13]

    S. Cen, Y. Chi, S. S. Du, and L. Xiao. Faster last-iterate convergence of policy optimization in zero-sum markov games. In The Eleventh International Conference on Learning Representations, 2023

    2023

  6. [14]

    S. Cen, J. Mei, K. Goshvadi, H. Dai, T. Yang, S. Yang, D. Schuurmans, Y. Chi, and B. Dai. Value-incentivized preference optimization: A unified approach to online and offline rlhf. arXiv preprint arXiv:2405.19320, 2024

    2024 arXiv

  7. [15]

    Z. Chen, D. Zhou, and Q. Gu. Almost optimal algorithms for two-player zero-sum linear mixture M arkov games. In International Conference on Algorithmic Learning Theory, pages 227--261. PMLR, 2022

    2022

  8. [16]

    Cheng, D

    S.-F. Cheng, D. M. Reeves, Y. Vorobeychik, and M. P. Wellman. Notes on equilibria in symmetric games. 2004

    2004

  9. [17]

    Q. Cui, K. Zhang, and S. Du. Breaking the curse of multiagents in a large state space: Rl in markov games with independent linear function approximation. In The Thirty Sixth Annual Conference on Learning Theory, pages 2651--2652. PMLR, 2023

    2023

  10. [18]

    Y. Dai, Q. Cui, and S. S. Du. Refined sample complexity for markov games with independent linear function approximation. arXiv preprint arXiv:2402.07082, 2024

    2024 arXiv

  11. [19]

    V. Dani, T. P. Hayes, and S. M. Kakade. Stochastic linear optimization under bandit feedback. In COLT, volume 2, page 3, 2008

    2008

  12. [20]

    Daskalakis and I

    C. Daskalakis and I. Panageas. Last-iterate convergence: Zero-sum games and constrained min-max optimization. arXiv preprint arXiv:1807.04252, 2018

    2018

  13. [21]

    Daskalakis, P

    C. Daskalakis, P. W. Goldberg, and C. H. Papadimitriou. The complexity of computing a N ash equilibrium. Communications of the ACM, 52 0 (2): 0 89--97, 2009

    2009

  14. [22]

    S. Du, S. Kakade, J. Lee, S. Lovett, G. Mahajan, W. Sun, and R. Wang. Bilinear classes: A structural framework for provable generalization in rl. In International Conference on Machine Learning, pages 2826--2836. PMLR, 2021

    2021

  15. [23]

    L. Erez, T. Lancewicki, U. Sherman, T. Koren, and Y. Mansour. Regret minimization and convergence to equilibria in general-sum M arkov games. In International Conference on Machine Learning, pages 9343--9373. PMLR, 2023

    2023

  16. [24]

    Gawlikowski, C

    J. Gawlikowski, C. R. N. Tassi, M. Ali, J. Lee, M. Humt, J. Feng, A. Kruspe, R. Triebel, P. Jung, R. Roscher, et al. A survey of uncertainty in deep neural networks. Artificial Intelligence Review, 56 0 (Suppl 1): 0 1513--1589, 2023

    2023

  17. [25]

    Huang, J

    B. Huang, J. D. Lee, Z. Wang, and Z. Yang. Towards general function approximation in zero-sum M arkov games. In International Conference on Learning Representations, 2022

    2022

  18. [26]

    Hung, P.-C

    Y.-H. Hung, P.-C. Hsieh, X. Liu, and P. Kumar. Reward-biased maximum likelihood estimation for linear stochastic bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 7874--7882, 2021

    2021

  19. [27]

    Z. Jia, L. Yang, C. Szepesvari, and M. Wang. Model-based reinforcement learning with value-targeted regression. In Learning for Dynamics and Control, pages 666--686. PMLR, 2020

    2020

  20. [28]

    C. Jin, Z. Allen-Zhu, S. Bubeck, and M. I. Jordan. Is q-learning provably efficient? Advances in neural information processing systems, 31, 2018

    2018

  21. [29]

    C. Jin, Z. Yang, Z. Wang, and M. I. Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on learning theory, pages 2137--2143. PMLR, 2020

    2020

  22. [30]

    C. Jin, Q. Liu, Y. Wang, and T. Yu. V-learning--a simple, efficient, decentralized algorithm for multiagent rl. arXiv preprint arXiv:2110.14555, 2021

    2021 arXiv

  23. [31]

    Kumar and A

    P. Kumar and A. Becker. A new family of optimal adaptive controllers for markov chains. IEEE Transactions on Automatic Control, 27 0 (1): 0 137--146, 1982

    1982

  24. [32]

    T. L. Lai. Adaptive treatment allocation and the multi-armed bandit problem. The annals of statistics, pages 1091--1114, 1987

    1987

  25. [33]

    G. Li, Y. Chi, Y. Wei, and Y. Chen. Minimax-optimal multi-agent rl in markov games with a generative model. In Proceedings of the 36th International Conference on Neural Information Processing Systems, pages 15353--15367, 2022

    2022

  26. [34]

    M. L. Littman. Markov games as a framework for multi-agent reinforcement learning. In Machine learning proceedings 1994, pages 157--163. Elsevier, 1994

    1994

  27. [35]

    Q. Liu, T. Yu, Y. Bai, and C. Jin. A sharp analysis of model-based reinforcement learning with self-play. In International Conference on Machine Learning, pages 7001--7010. PMLR, 2021

    2021

  28. [36]

    Liu, P.-C

    X. Liu, P.-C. Hsieh, Y. H. Hung, A. Bhattacharya, and P. Kumar. Exploration through reward biasing: Reward-biased maximum likelihood estimation for stochastic multi-armed bandits. In International Conference on Machine Learning, pages 6248--6258. PMLR, 2020

    2020

  29. [37]

    Z. Liu, M. Lu, W. Xiong, H. Zhong, H. Hu, S. Zhang, S. Zheng, Z. Yang, and Z. Wang. Maximize to explore: One objective function fusing estimation, planning, and exploration. Advances in Neural Information Processing Systems, 36, 2024

    2024

  30. [38]

    Mao and T

    W. Mao and T. Ba s ar. Provably efficient reinforcement learning in decentralized general-sum M arkov games. Dynamic Games and Applications, 13 0 (1): 0 165--186, 2023

    2023

  31. [39]

    R. D. McKelvey and T. R. Palfrey. Quantal response equilibria for normal form games. Games and economic behavior, 10 0 (1): 0 6--38, 1995

    1995

  32. [40]

    J. Mei, C. Xiao, C. Szepesvari, and D. Schuurmans. On the global convergence rates of softmax policy gradient methods. In International conference on machine learning, pages 6820--6829. PMLR, 2020

    2020

  33. [41]

    Mertikopoulos, C

    P. Mertikopoulos, C. Papadimitriou, and G. Piliouras. Cycles in adversarial regularized learning. In Proceedings of the twenty-ninth annual ACM-SIAM symposium on discrete algorithms, pages 2703--2717. SIAM, 2018

    2018

  34. [42]

    A. Mete, R. Singh, X. Liu, and P. Kumar. Reward biased maximum likelihood estimation for reinforcement learning. In Learning for Dynamics and Control, pages 815--827. PMLR, 2021

    2021

  35. [43]

    A. Modi, N. Jiang, A. Tewari, and S. Singh. Sample complexity of reinforcement learning using linearly combined model ensembles. In International Conference on Artificial Intelligence and Statistics, pages 2010--2020. PMLR, 2020

    2010

  36. [44]

    Munos, M

    R. Munos, M. Valko, D. Calandriello, M. G. Azar, M. Rowland, Z. D. Guo, Y. Tang, M. Geist, T. Mesnard, A. Michi, et al. Nash learning from human feedback. arXiv preprint arXiv:2312.00886, 2023

    2023 arXiv

  37. [45]

    J. F. Nash. Non-cooperative games. 1950

    1950

  38. [46]

    C. Ni, Y. Song, X. Zhang, C. Jin, and M. Wang. Representation learning for general-sum low-rank markov games. arXiv preprint arXiv:2210.16976, 2022

    2022 arXiv

  39. [47]

    O'Donoghue

    B. O'Donoghue. Variational bayesian reinforcement learning with regret bounds. Advances in Neural Information Processing Systems, 34: 0 28208--28221, 2021

    2021

  40. [48]

    O’Donoghue, T

    B. O’Donoghue, T. Lattimore, and I. Osband. Matrix games with bandit feedback. In Uncertainty in Artificial Intelligence, pages 279--289. PMLR, 2021

    2021

  41. [49]

    D. J. Russo, B. Van Roy, A. Kazerouni, I. Osband, Z. Wen, et al. A tutorial on thompson sampling. Foundations and Trends in Machine Learning , 11 0 (1): 0 1--96, 2018

    2018

  42. [50]

    P. G. Sessa, M. Kamgarpour, and A. Krause. Efficient model-based multi-agent reinforcement learning via optimistic equilibrium computation. In International Conference on Machine Learning, pages 19580--19597. PMLR, 2022

    2022

  43. [51]

    L. S. Shapley. Stochastic games. Proceedings of the National Academy of Sciences, 39 0 (10): 0 1095--1100, 1953

    1953

  44. [52]

    Sokota, R

    S. Sokota, R. D'Orazio, J. Z. Kolter, N. Loizou, M. Lanctot, I. Mitliagkas, N. Brown, and C. Kroer. A unified approach to reinforcement learning, quantal response equilibria, and two-player zero-sum games. arXiv preprint arXiv:2206.05825, 2022

    2022 arXiv

  45. [53]

    Z. Song, S. Mei, and Y. Bai. When can we learn general-sum markov games with a large number of players sample-efficiently? arXiv preprint arXiv:2110.04184, 2021

    2021 arXiv

  46. [54]

    Swamy, C

    G. Swamy, C. Dann, R. Kidambi, Z. S. Wu, and A. Agarwal. A minimaximalist approach to reinforcement learning from human feedback. arXiv preprint arXiv:2401.04056, 2024

    2024 arXiv

  47. [55]

    Y. Wang, R. Wang, S. S. Du, and A. Krishnamurthy. Optimism in reinforcement learning with generalized linear function approximation. arXiv preprint arXiv:1912.04136, 2019

    1912 arXiv

  48. [56]

    Y. Wang, Q. Liu, Y. Bai, and C. Jin. Breaking the curse of multiagency: Provably efficient decentralized multi-agent rl with function approximation. In The Thirty Sixth Annual Conference on Learning Theory, pages 2793--2848. PMLR, 2023

    2023

  49. [57]

    Wei, C.-W

    C.-Y. Wei, C.-W. Lee, M. Zhang, and H. Luo. Linear last-iterate convergence in constrained saddle-point optimization. arXiv preprint arXiv:2006.09517, 2020

    2006 arXiv

  50. [58]

    Q. Xie, Y. Chen, Z. Wang, and Z. Yang. Learning zero-sum simultaneous-move markov games using function approximation and correlated equilibrium. In Conference on learning theory, pages 3674--3682. PMLR, 2020

    2020

  51. [59]

    Yang and M

    L. Yang and M. Wang. Sample-optimal parametric q-learning using linearly additive features. In International conference on machine learning, pages 6995--7004. PMLR, 2019

    2019

  52. [60]

    T. Yang, S. Cen, Y. Wei, Y. Chen, and Y. Chi. Federated natural policy gradient and actor critic methods for multi-task reinforcement learning. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024 a

    2024

  53. [61]

    T. Yang, J. Mei, H. Dai, Z. Wen, S. Cen, D. Schuurmans, Y. Chi, and B. Dai. Faster wind: Accelerating iterative best-of- n distillation for llm alignment. arXiv preprint arXiv:2410.20727, 2024 b

    2024 arXiv

  54. [62]

    R. Yuan, S. S. Du, R. M. Gower, A. Lazaric, and L. Xiao. Linear convergence of natural policy gradient methods with log-linear policies. In International Conference on Learning Representations, 2023

    2023

  55. [63]

    W. Zhan, S. Cen, B. Huang, Y. Chen, J. D. Lee, and Y. Chi. Policy mirror descent for regularized reinforcement learning: A generalized framework with linear convergence. SIAM Journal on Optimization, 33 0 (2): 0 1061--1091, 2023

    2023

  56. [64]

    Zhang, Q

    R. Zhang, Q. Liu, H. Wang, C. Xiong, N. Li, and Y. Bai. Policy optimization for M arkov games: Unified framework and faster convergence. Advances in Neural Information Processing Systems, 35: 0 21886--21899, 2022

    2022

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.