Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback

We introduce OPO-CMDP, the first policy optimization algorithm for stochastic Contextual Markov Decision Process (CMDPs) under general offline function approximation. Our approach achieves a high probability regret bound of O(H 4 T |S||A| log(|F||P|)), where S and A denote the state and action spaces, H the horizon length, T the number of episodes, and F, P the finite function classes used to approximate the losses and dynamics, respectively. This is the first regret bound with optimal dependence on |S| and |A|, directly improving the current state-of-theart (Qian, Hu, and Simchi-Levi, 2024) . These results demonstrate that optimistic policy optimization provides a natural, computationally superior and theoretically near-optimal path for solving CMDPs.