Asymptotic Instance-Optimal Algorithms for Interactive Decision Making

Bandit and reinforcement learning (RL) algorithms demonstrated a wide range of successful real-life applications [Silver et al., 2016, 2017, Mnih et al., 2013, Berner et al., 2019, Vinyals et al., 2019, Mnih et al., 2015, Degrave et al., 2022]. Past works have theoretically studied the regret or sample complexity of various interactive decision making problems, such as contextual bandits, reinforcement learning (RL), partially observable Markov decision process (see Azar et al. [2017], Jin et al. [2018], Dong et al. [2021], Li et al. [2019], Agarwal et al. [2014], Foster and Rakhlin [2020], Jin et al. [2020], and references therein). Recently, Foster et al. [2021] present a unified algorithmic principle for achieving the minimax regret--the optimal regret for the worst-case problem instances. However, minimax regret bounds do not necessarily always present a full picture of the statistical complexity of the problem. They characterize the complexity of the most difficult instances, but potentially many other instances are much easier. An ideal algorithm should adapt to the complexity of a particular instance and incur smaller regrets on easy instances than the worst-case instances. Thus, an ideal regret bound should be instance-dependent, that is, depending on some properties of each instance. Prior works designed algorithms with instance-dependent regret bounds that are stronger than minimax regret bounds, but they are often not directly comparable because they depend on different properties of the instances, such as the gap conditions and the variance of the value function [Zanette and Brunskill, 2019, Xu et al., 2021, Foster et al., 2020, Tirinzoni et al., 2021]. A more ambitious and challenging goal is to design instance-optimal algorithms that outperform, on every instance, all consistent algorithms (those achieving non-trivial regrets on all instances).