# Model Selection for Average Reward RL with Application to Utility Maximization in Repeated Games

arXiv: https://arxiv.org/abs/2411.06069 · HTML: https://mlsanity.com/paper/2411.06069/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 41 references that are in the map.
- First posted on arXiv 9 Nov 2024.

## Builds on (most cited first, 29 of 29)

- [V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RL](https://mlsanity.com/paper/2110.14555/) (2021)
- [Corralling a Band of Bandit Algorithms](https://mlsanity.com/paper/1612.06246/) (2016)
- [Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium](https://mlsanity.com/paper/2002.07066/) (2020)
- [Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes](https://mlsanity.com/paper/1910.07072/) (2019)
- [Online Reinforcement Learning in Stochastic Games](https://mlsanity.com/paper/1712.00579/) (2017)
- [Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learning](https://mlsanity.com/paper/1802.04020/) (2018)
- [Model selection for contextual bandits](https://mlsanity.com/paper/1906.00531/) (2019)
- [Strategizing against No-regret Learners](https://mlsanity.com/paper/1909.13861/) (2019)
- [The Complexity of Markov Equilibrium in Stochastic Games](https://mlsanity.com/paper/2204.03991/) (2022)
- [Regret Bound Balancing and Elimination for Model Selection in Bandits and RL](https://mlsanity.com/paper/2012.13045/) (2020)
- [Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Function](https://mlsanity.com/paper/1906.05110/) (2019)
- [Selling to a No-Regret Buyer](https://mlsanity.com/paper/1711.09176/) (2017)
- [Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPs](https://mlsanity.com/paper/1803.01626/) (2018)
- [On Lower Bounds for Regret in Reinforcement Learning](https://mlsanity.com/paper/1608.02732/) (2016)
- [Parameter-free online learning via model selection](https://mlsanity.com/paper/1801.00101/) (2017)
- [Tightening Exploration in Upper Confidence Reinforcement Learning](https://mlsanity.com/paper/2004.09656/) (2020)
- [The Pareto Frontier of model selection for general Contextual Bandits](https://mlsanity.com/paper/2110.13282/) (2021)
- [Can Reinforcement Learning Find Stackelberg-Nash Equilibria in General-Sum Markov Games with Myopic Followers?](https://mlsanity.com/paper/2112.13521/) (2021)
- [Regret Balancing for Bandit and RL Model Selection](https://mlsanity.com/paper/2006.05491/) (2020)
- [Is Learning in Games Good for the Learners?](https://mlsanity.com/paper/2305.19496/) (2023)
- [Regret Bounds for Reinforcement Learning via Markov Chain Concentration](https://mlsanity.com/paper/1808.01813/) (2018)
- [Improved Analysis of UCRL2 with Empirical Bernstein Inequality](https://mlsanity.com/paper/2007.05456/) (2020)
- [Achieving Tractable Minimax Optimal Regret in Average Reward MDPs](https://mlsanity.com/paper/2406.01234/) (2024)
- [Near Optimal Exploration-Exploitation in Non-Communicating Markov Decision Processes](https://mlsanity.com/paper/1807.02373/) (2018)
- [Maximizing utility in multi-agent environments by anticipating the behavior of other learners](https://mlsanity.com/paper/2407.04889/) (2024)
- [Policy Regret in Repeated Games](https://mlsanity.com/paper/1811.04127/) (2018)
- [Towards Costless Model Selection in Contextual Bandits: A Bias-Variance Perspective](https://mlsanity.com/paper/2106.06483/) (2021)
- [Learning in Markov Games with Adaptive Adversaries: Policy Regret, Fundamental Barriers, and Efficient Algorithms](https://mlsanity.com/paper/2411.00707/) (2024)
- [Model Selection for Generic Reinforcement Learning](https://mlsanity.com/paper/2107.05849/) (2021)

## Built on by (most cited first, 1 of 1)

- [Computational Intractability of Strategizing against Online Learners](https://mlsanity.com/paper/2503.04202/) (2025)

## Abstract (arXiv)

In standard RL, a learner attempts to learn an optimal policy for a Markov Decision Process whose structure (e.g. state space) is known. In online model selection, a learner attempts to learn an optimal policy for an MDP knowing only that it belongs to one of M >1 model classes of varying complexity. Recent results have shown that this can be feasibly accomplished in episodic online RL. In this work, we propose mathsfMRBEAR, an online model selection algorithm for the average reward RL setting. The regret of the algorithm is in tilde O(M Cm^*2 mathsfBm^*(T,δ)) where Cm^* represents the complexity of the simplest well-specified model class and mathsfBm^*(T,δ) is its corresponding regret bound. This result shows that in average reward RL, like the episodic online RL, the additional cost of model selection scales only linearly in M, the number of model classes. We apply mathsfMRBEAR to the interaction between a learner and an opponent in a two-player simultaneous general-sum repeated game, where the opponent follows a fixed unknown limited memory strategy. The learner's goal is to maximize its utility without knowing the opponent's utility function. The interaction is over T rounds with no episode or discounting which leads us to measure the learner's performance by average reward regret. In this application, our algorithm enjoys an opponent-complexity-dependent regret in tilde O(M(mathsfsp(h^*) Bm^* Am^*+1)^frac32 √T), where m^*≤ M is the unknown memory limit of the opponent, mathsfsp(h^*) is the unknown span of optimal bias induced by the opponent, and A and B are the number of actions for the learner and opponent respectively. We also show that the exponential dependency on m^* is inevitable by proving a lower bound on the learner's regret.