Constrained Upper Confidence Reinforcement Learning
This addresses safe exploration in unknown environments for applications like robotics, though it is incremental as it builds on existing upper confidence methods.
The paper tackles the problem of reinforcement learning with unknown reward and cost constraints but known transition dynamics, presenting the C-UCRL algorithm that achieves sub-linear regret of O(T^(3/4)√log(T/δ)) while satisfying constraints with high probability.
Constrained Markov Decision Processes are a class of stochastic decision problems in which the decision maker must select a policy that satisfies auxiliary cost constraints. This paper extends upper confidence reinforcement learning for settings in which the reward function and the constraints, described by cost functions, are unknown a priori but the transition kernel is known. Such a setting is well-motivated by a number of applications including exploration of unknown, potentially unsafe, environments. We present an algorithm C-UCRL and show that it achieves sub-linear regret ($ O(T^{\frac{3}{4}}\sqrt{\log(T/δ)})$) with respect to the reward while satisfying the constraints even while learning with probability $1-δ$. Illustrative examples are provided.