A General Framework for Sequential Decision-Making under Adaptivity Constraints
This work addresses the problem of reducing computational and data efficiency burdens in reinforcement learning for researchers and practitioners, though it is incremental as it builds on prior models with new constraints.
The paper tackles sequential decision-making under adaptivity constraints like rare policy switch and batch learning, introducing a general framework called the Eluder Condition class that covers various reinforcement learning models, and provides algorithms achieving logarithmic switching cost with sublinear regret for rare policy switch and a regret bound scaling with the number of batches for batch learning.
We take the first step in studying general sequential decision-making under two adaptivity constraints: rare policy switch and batch learning. First, we provide a general class called the Eluder Condition class, which includes a wide range of reinforcement learning classes. Then, for the rare policy switch constraint, we provide a generic algorithm to achieve a $\widetilde{\mathcal{O}}(\log K) $ switching cost with a $\widetilde{\mathcal{O}}(\sqrt{K})$ regret on the EC class. For the batch learning constraint, we provide an algorithm that provides a $\widetilde{\mathcal{O}}(\sqrt{K}+K/B)$ regret with the number of batches $B.$ This paper is the first work considering rare policy switch and batch learning under general function classes, which covers nearly all the models studied in the previous works such as tabular MDP (Bai et al. 2019; Zhang et al. 2020), linear MDP (Wang et al. 2021; Gao et al. 2021), low eluder dimension MDP (Kong et al. 2021; Gao et al. 2021), generalized linear function approximation (Qiao et al. 2023), and also some new classes such as the low $D_Δ$-type Bellman eluder dimension problem, linear mixture MDP, kernelized nonlinear regulator and undercomplete partially observed Markov decision process (POMDP).