Bellman-Convex Reinforcement Learning in Continuous Markov Decision Processes

Reinforcement learning in continuous state and action spaces faces two fundamental challenges: sample complexity grows exponentially with dimension, while planning may require high-dimensional nonconvex optimization over continuous actions. Yet many real-world problems in operations and control possess exploitable convex structure. We introduce Bellman convexity, a Bellman-operator-level framework under which Bellman updates preserve convexity and Lipschitz continuity of both Q functions and value functions, capturing a broad family of convex sequential decision making problems arising in robotics, autonomous systems, and energy systems. Under generative-model access, we develop Bellman envelope regression (BER), which adaptively samples proximal anchors of noisy Bellman targets and converts the anchor values into global convex envelopes. Embedding BER in fitted Q-iteration yields fixed-discount sample complexity O(epsilon^-2-(d_s+d_a)/2) for uniform recovery of Q*, and we prove a matching lower bound in the epsilon-accuracy exponent. Counterintuitively, we uncover a sharp separation from standard RL theory: Bellman convexity makes policy learning statistically easier than uniform Q* recovery by removing the action dimension from the accuracy exponent. An epsilon-optimal policy can be learned with O(epsilon^-2-d_s/2) samples, matching the fixed-discount lower bound. Finally, we show that the deterministic planning steps used by our algorithms are convex programs and, under standard linear or conic descriptions, admit LP, SOCP, or SDP formulations.