A Reduction-Based Framework for Conservative Bandits and Reinforcement Learning
This work addresses the challenge of ensuring safe exploration in sequential decision-making for researchers and practitioners in machine learning, though it is incremental as it builds on existing conservative methods.
The paper tackles the problem of conservative decision-making in bandits and reinforcement learning by introducing a reduction-based framework that calculates the necessary budget from a baseline policy. It improves lower bounds for several settings and provides new or tighter upper bounds with simpler analyses.
In this paper, we present a reduction-based framework for conservative bandits and RL, in which our core technique is to calculate the necessary and sufficient budget obtained from running the baseline policy. For lower bounds, we improve the existing lower bound for conservative multi-armed bandits and obtain new lower bounds for conservative linear bandits, tabular RL and low-rank MDP, through a black-box reduction that turns a certain lower bound in the nonconservative setting into a new lower bound in the conservative setting. For upper bounds, in multi-armed bandits, linear bandits and tabular RL, our new upper bounds tighten or match existing ones with significantly simpler analyses. We also obtain a new upper bound for conservative low-rank MDP.