acceptodds
Under review as a conference paper at ICLR 2027

Bellman-Convex Reinforcement Learning in Continuous Markov Decision Processes

Abstract

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.

Primary area:
learning theory
Keywords:
Reinforcement Learning, Sample Complexity, Generative Model, Markov Decision Processes

Reviews

Among:
Shape:
1234this paper, Top 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.67 over 3 reviews, above 99% of the others.
Reviewer_oQMDOpenReview ↗
Rating
4
Confidence
3
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This paper develops initial understanding of general convex MDPs: continuous MDPs where the Q/value functions become convex state-action/state space. The paper develops an algorithm, Bellman Envelope Regression, for non-parametrically approximating the Q-function of a convex MDP. The paper analyzes the sample complexity of the proposed algorithm and shows sharpness against a worst-case example. The paper then discusses the idea of applying the Q-function representation used in BER to value functions and shows that joint convexity of the Q-function in state-action space allows a non-parametric representation of the value function in state space by anchoring on specific states while the actions are inf-projected on the fly. This eliminates the exponential scaling of the grid in the action direction. Finally, the paper shows the algorithm is implementable and scales as expected on some toy examples.

Critical strengths

Elegant algorithm and theory. Great structural insights. (This section is a bit thin, but a lot more discussion of strengths ended up in the weaknesses section)

Critical weaknesses

I would not call the weaknesses of this paper critical in the sense that there's nothing seriously blocking acceptance and I don't want to condition my decision on the authors adopting my recommendations --- I believe the insights of this paper are both interesting and important enough to be published as is. That being said, I think the high level story misses the point and can be told in a much better way. I hope the authors take the following into consideration. It seems that the high-level take here is that this is a study of sample complexity. On the surface, the story reads as follows "Here's some alogrithm for solving Bellman-convex MDPs. This algorithm manages to reduce the exponent of the sample complexity term by half over the generic case. Sadly, this is optimal. Oh by the way, here's one cool thing about value function representations." After my first read of the paper, my thoughts were that the results are underwhelming and the only surprise here is how boring this class is. I was ready to give the paper a lukewarm review but I thought that I should try to engage with the theory at least a bit, so I decided to skimp through the main poof ideas. I'm so glad I did, because the theory is genuinely quite cool (which wasn't obvious from the main text). Essentially what happens in the BER algorithm is that three things interact:

  1. A non-parametric representation of the Q-function via supporting hyperplanes (subgradients).
  2. Quadratic Bellman residual minimization via FQI.
  3. Soft cutting-plane generation via proximal Moreau-Yosida regularized search. I think there's a really interesting thing going on here and burying it inside of a sample complexity argument doesn't do it justice. These three things are in some sense compatible with each other due to the underlying Bellman convexity, and it feels like this could happen so naturally only in this type of structure (or some generalization thereof). This seems like a major structural insight about the class hidden in the appendix.

On the other hand, the sample efficiency bounds constructed are rely on degenerate dynamics, showing that worst-case statistical efficiency comes from unstructured examples, which is not particularly interesting. I would suggest the following restructuring:

  1. Give more space to the insights about representational complexity of a Bellman convex MDP's Q function and the involved machinery. The algorithm is then just a greedy materialization of this representation.
  2. Demote the sample complexity lower bounds to sanity checks.
  3. Potentially compress section 4 --- if the reader understands the main structural idea, the theory in sec. 4 is relatively straightforward.
Questions for authors
  1. One thing this paper might have missed --- it seems to me that a major categorical difference between convex mdps and arbitrary mdps is that in the non-convex case, action minimization in the Bellman operator destroys smoothness whereas in convex ones, if the costs are (or can be regularized to be) strongly convex and the dynamics are non-trivial, min_a (acting as an infimal convolution) and ES′\mathbb{E}_{S'} become cooperative smoothing/regularizing operators. I thus expect that Q-functions of convex MDPs would tend towards smoothness naturally, and I imagine this would be a major driver for algorithmic efficiency. The authors might want to look a little bit into this, just as an observation if nothing else.

  2. LLM review discovered something that might be a real bug. I don't think it changes the message, but I advise the authors to take a look, as well as take a look at Deep Reviews outputs (I believe this is accessible via the ICLR submission page), as it seems to flag a few smaller things. I'm pasting a summary of the bug below:

In Appendix C (around line 721), the sum of per-round budgets seems to bound G_K = Σ_j γ^{aj} by (1−γ)^{−a}. Since 1 − γ^a ≥ a(1−γ) and γ^a ≥ γ, G_K is Θ(1/(1−γ)) as γ → 1, which would raise the (1−γ) exponent in Theorem 3.1 by one. The same step seems to appear in Appendix E (around line 1219) for Theorem 4.1. This doesn't affect the ε-rate, but could the authors check the horizon dependence?

Reviewer_gpAGOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper considers the fitted Q-learning algorithm in continuous MDPs under the assumption of Bellman convexity. The authors propose the BER-FQI algorithm for Q learning and establish matching upper and lower bounds for the sample complexity of the learned Q function, which is ϵ−2−(ds+da)/2\epsilon^{-2-(ds+da)/2}. Furthermore, the authors extend their framework to policy learning via STATE-BER-VI, achieving sample complexity ϵ−2−(ds)/2\epsilon^{-2-(ds)/2}

The key methodological distinction lies in the domain of proximal optimization. BER-FQI performs optimization in the action-value function space, whereas STATE-BER-VI operates in the value function space

Critical strengths
  1. The paper presents a solid progression, starting from Q learning via BER and extending to policy learning, and the sample complexity for policy learning can be independent of the action space dimension.
  2. To the best of our knowledge, this is the first work to establish sample complexity bounds for continuous MDPs under Bellman convexity.
Critical weaknesses
  1. Bellman convexity is a restrictive condition. The framework cannot be applied to general RL case such as tabular MDPs or non-convex systems such as standard control tasks.
  2. The experiments lack comparisons with other state-of-the-art continuous RL baselines(SAC, FQI) .
Questions for authors
  1. Why does the convergence slope of STATE-BER-VI in Figure 2(b) appear more sensitive to increases in d_a compared to BER-FQI?
  2. Could the authors highlight the technical contributions, both in algorithmic design and in the proofs from existing works in RL or standard convex regression?
  3. How would the proposed algorithms perform in environments where Bellman convexity does not hold? Could the authors provide experimental results on standard continuous RL benchmarks, such as MuJoCo.
Reviewer_wpSYOpenReview ↗
Rating
4(+1)
Confidence
2
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

In this paper the authors attempt to resolve two substantial issues in Reinforcement Learning where the state spaces and action spaces are continuous: The first one is statistical and relates to the curse of dimensionality, where the sample complexity of previous approaches grows exponentially with the joint state-action space dimension (ds+dad_s + d_a). The second barrier is computational, relates to evaluating optimal policies, which requires the global minimisation of continuous value functions that are generally non-convex in standard continuous MDPs. The authors mitigate both barriers by introducing Bellman Convexity; the latter guarantees that Bellman updates naturally preserve both the convexity and Lipschitz continuity of action-value (QQ) and state-value (VV) functions across infinite-horizon iterations.

Critical strengths
  • I find the theoretical breakthroughs quite significant in this paper. The authors halve the statistical sample complexity exponent for uniform Q⋆Q^\star estimation, and remove the action dimension dad_a entirely from the exponent for policy learning.
  • The authors also establish minimax lower bounds to show that these sample complexity exponents cannot be improved further under all the stated assumptions (including generative-model access and fixed discount factor).
Critical weaknesses
  • The experiments are illustrative, and the paper does not empirically benchmark against either modern deep continuous RL algorithms such as continuous actor-critic methods or simpler non-convex FQI / discretised baselines, which I think, if done, would help in positioning this line of work on the practical side beyond what the theory suggests. Specifically, this would visually validate the sample complexity advantage and the inference latency related to solving a deterministic convex program at runtime for every single state query.
  • Additionally, some strong practical insights could be revealed regarding the sensitivity of the oracle if there were experiments on how policy quality degrades–and the corresponding effect on sample complexity–when the empirical generative model is constructed from a varying number of observations, rather than only 8,760.
Questions for authors
  • Do the authors think that a similar advantage can be achieved on non-i.i.d. trajectory data, and what indicates so?
  • What happens if the domain diameter DD of the state–action space X\mathcal{X} is unknown a priori? Similarly (and more importantly), what happens if the Lipschitz constants are unknown?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.