Provably Efficient Model-Free Constrained RL with Linear Function Approximation
We study the constrained reinforcement learning problem, in which an agent
aims to maximize the expected cumulative reward subject to a constraint on the
expected total value of a utility function. In contrast to existing model-based
approaches or model-free methods accompanied with a `simulator', we aim to
develop the first model-free, simulator-free algorithm that achieves a
sublinear regret and a sublinear constraint violation even in large-scale
systems. To this end, we consider the episodic constrained Markov decision
processes with linear function approximation, where the transition dynamics and
the reward function can be represented as a linear function of some known
feature mapping. We show that $\tilde{\mathcal{O}}(\sqrt{d^3H^3T})$ regret and
$\tilde{\mathcal{O}}(\sqrt{d^3H^3T})$ constraint violation bounds can be
achieved, where $d$ is the dimension of the feature mapping, $H$ is the length
of the episode, and $T$ is the total number of steps. Our bounds are attained
without explicitly estimating the unknown transition model or requiring a
simulator, and they depend on the state space only through the dimension of the
feature mapping. Hence our bounds hold even when the number of states goes to
infinity. Our main results are achieved via novel adaptations of the standard
LSVI-UCB algorithms. In particular, we first introduce primal-dual optimization
into the LSVI-UCB algorithm to balance between regret and constraint violation.
More importantly, we replace the standard greedy selection with respect to the
state-action function in LSVI-UCB with a soft-max policy. This turns out to be
key in establishing uniform concentration for the constrained case via its
approximation-smoothness trade-off. We also show that one can achieve an even
zero constraint violation while still maintaining the same order with respect
to $T$.