Combining No-regret And Q-learning

Abstract

Counterfactual Regret Minimization (CFR) has found success in settings like poker which have both terminal states and perfect recall. We seek to understand how to relax these requirements. As a first step, we introduce a simple algorithm, local no-regret learning (LONR), which uses a Q-learning-like update rule to allow learning without terminal states or perfect recall. We prove its convergence for the basic case of MDPs (and limited extensions of them) and present empirical results showing that it achieves last iterate convergence in a number of settings, most notably NoSDE games, a class of Markov games specifically designed to be challenging to learn where no prior algorithm is known to achieve convergence to a stationary equilibrium even on average.

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keykash2019combining

Related papers

• Easy As Abcs: Unifying Boltzmann Q-learning And Counterfactual Regret Minimization (2024)0.00
• Regret Minimization And Convergence To Equilibria In General-sum Markov Games (2022)0.00
• Model-free Online Learning In Unknown Sequential Decision Making Problems And Games (2021)5.24
• Decentralized Model-free Reinforcement Learning In Stochastic Games With Average-reward Objective (2023)0.00
• Regret Bounds For Decentralized Learning In Cooperative Multi-agent Dynamical Systems (2020)0.00
• Near Optimal Convergence To Coarse Correlated Equilibrium In General-sum Markov Games (2025)0.00
• On The Impossibility Of Convergence Of Mixed Strategies With No Regret Learning (2020)0.00
• Sublinear Regret For A Class Of Continuous-time Linear-quadratic Reinforcement Learning Problems (2024)0.00