Asymptotic Instance-Optimal Algorithms for Interactive Decision Making
Past research on interactive decision making problems (bandits, reinforcement
learning, etc.) mostly focuses on the minimax regret that measures the
algorithm's performance on the hardest instance. However, an ideal algorithm
should adapt to the complexity of a particular problem instance and incur
smaller regrets on easy instances than worst-case instances. In this paper, we
design the first asymptotic instance-optimal algorithm for general interactive
decision making problems with finite number of decisions under mild conditions.
On \textit{every} instance $f$, our algorithm outperforms \emph{all} consistent
algorithms (those achieving non-trivial regrets on all instances), and has
asymptotic regret $\mathcal{C}(f) \ln n$, where $\mathcal{C}(f)$ is an exact
characterization of the complexity of $f$. The key step of the algorithm
involves hypothesis testing with active data collection. It computes the most
economical decisions with which the algorithm collects observations to test
whether an estimated instance is indeed correct; thus, the complexity
$\mathcal{C}(f)$ is the minimum cost to test the instance $f$ against other
instances. Our results, instantiated on concrete problems, recover the
classical gap-dependent bounds for multi-armed bandits [Lai and Robbins, 1985]
and prior works on linear bandits [Lattimore and Szepesvari, 2017], and improve
upon the previous best instance-dependent upper bound [Xu et al., 2021] for
reinforcement learning.