- 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:
- A non-parametric representation of the Q-function via supporting hyperplanes (subgradients).
- Quadratic Bellman residual minimization via FQI.
- 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:
- 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.
- Demote the sample complexity lower bounds to sanity checks.
- Potentially compress section 4 --- if the reader understands the main structural idea, the theory in sec. 4 is relatively straightforward.
Questions for authors
-
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 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.
-
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?