Timezone: »

Provably Efficient Model-Free Constrained RL with Linear Function Approximation
Arnob Ghosh · Xingyu Zhou · Ness Shroff

Thu Dec 01 02:00 PM -- 04:00 PM (PST) @ Hall J #540
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 \emph{model-free}, \emph{simulator-free} algorithm that achieves a sublinear regret and a sublinear constraint violation even in \emph{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 with a soft-max policy. This turns out to be key in establishing uniform concentration (a critical step for provably efficient model-free exploration) for the constrained case via its approximation-smoothness trade-off. Finally, we also show that one can achieve an even zero constraint violation for large enough $T$ by trading the regret a little bit but still maintaining the same order with respect to $T$.

Author Information

Arnob Ghosh (The Ohio State University, Columbus)

Current Position: Research Scientist at the Ohio State University (Dept. of Electrical and Computer Engineering); host is Ness Shroff since June 2021. Assistant Professor at IIT-Delhi from August 2019 -- June 2021 Post-Doc at Purdue University from August 2016 -- June 2019 Ph.D. from University of Pennsylvania in August 2016

Xingyu Zhou (Wayne State University)
Ness Shroff (The Ohio State University)

More from the Same Authors