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

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.