Reproduce “Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximation” on OpenResearch

About this paper

Toshinori Kitamura, Arnob Ghosh, Tadashi Kozuno, Wataru Kumagai, Kazumi Kasaura, Kenta Hoshino, Yohei Hosoe, Yutaka Matsuo

Researchers introduce OPSE-LCMDP, an algorithm for Constrained Markov Decision Processes with linear function approximation, delivering provably sublinear regret and episode-wise zero constraint violation. This method enables computationally efficient safe reinforcement learning for large-scale problems, scaling polynomially with feature dimension, horizon, and action space size, independent of the state space.

Key insights

• A confidence-based, limited deployment mechanism for a known safe policy can ensure feasibility in early exploration without incurring excessive regret in linear CMDPs.
• Softmax-based policies, combined with a bisection search over a regularization parameter, provide a scalable and robust alternative to traditional LP or Lagrangian methods for enforcing hard constraints with function approximation.
• The use of clipped value functions is essential for maintaining stable value estimates and preventing error propagation in linear function approximation settings under constraints.

Summary by alphaXiv.