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

Alireza Masoumian, James R. Wright
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:4303-4311, 2026.

Abstract

In standard RL, the structure of the Markov Decision Process (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 $\textsf{MRBEAR}$, an online model selection algorithm for the average reward RL setting which is based on the idea of regret balancing and elimination. The regret of the algorithm is in $\tilde O(M C_{m*}^2 B_{m*}(T,\delta))$ where $C_{m*}$ represents the complexity of the simplest well-specified model class and $B_{m^*}(T,\delta)$ is its corresponding regret bound. This result shows that in average reward RL, the additional cost of model selection scales only linearly in $M$, the number of model classes. As an application, in a simultaneous general-sum repeated game, where the opponent follows a fixed unknown limited memory strategy, the learner can maximize its utility using $\textsf{MRBEAR}$. By proving a lower bound, we showed the learner’s regret is tight in opponent’s memory order. In addition, the algorithm’s performance is demonstrated through experiments.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-masoumian26a, title = { Model Selection for Average Reward RL with Application to Utility Maximization in Repeated Games }, author = {Masoumian, Alireza and Wright, James R.}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {4303--4311}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/masoumian26a/masoumian26a.pdf}, url = {https://proceedings.mlr.press/v300/masoumian26a.html}, abstract = { In standard RL, the structure of the Markov Decision Process (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 $\textsf{MRBEAR}$, an online model selection algorithm for the average reward RL setting which is based on the idea of regret balancing and elimination. The regret of the algorithm is in $\tilde O(M C_{m*}^2 B_{m*}(T,\delta))$ where $C_{m*}$ represents the complexity of the simplest well-specified model class and $B_{m^*}(T,\delta)$ is its corresponding regret bound. This result shows that in average reward RL, the additional cost of model selection scales only linearly in $M$, the number of model classes. As an application, in a simultaneous general-sum repeated game, where the opponent follows a fixed unknown limited memory strategy, the learner can maximize its utility using $\textsf{MRBEAR}$. By proving a lower bound, we showed the learner’s regret is tight in opponent’s memory order. In addition, the algorithm’s performance is demonstrated through experiments. } }
Endnote
%0 Conference Paper %T Model Selection for Average Reward RL with Application to Utility Maximization in Repeated Games %A Alireza Masoumian %A James R. Wright %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-masoumian26a %I PMLR %P 4303--4311 %U https://proceedings.mlr.press/v300/masoumian26a.html %V 300 %X In standard RL, the structure of the Markov Decision Process (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 $\textsf{MRBEAR}$, an online model selection algorithm for the average reward RL setting which is based on the idea of regret balancing and elimination. The regret of the algorithm is in $\tilde O(M C_{m*}^2 B_{m*}(T,\delta))$ where $C_{m*}$ represents the complexity of the simplest well-specified model class and $B_{m^*}(T,\delta)$ is its corresponding regret bound. This result shows that in average reward RL, the additional cost of model selection scales only linearly in $M$, the number of model classes. As an application, in a simultaneous general-sum repeated game, where the opponent follows a fixed unknown limited memory strategy, the learner can maximize its utility using $\textsf{MRBEAR}$. By proving a lower bound, we showed the learner’s regret is tight in opponent’s memory order. In addition, the algorithm’s performance is demonstrated through experiments.
APA
Masoumian, A. & Wright, J.R.. (2026). Model Selection for Average Reward RL with Application to Utility Maximization in Repeated Games . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:4303-4311 Available from https://proceedings.mlr.press/v300/masoumian26a.html.

Related Material