Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors consider value iteration [TJ](x) = min_u [c(x,u) + gamma E J(x’)] for problems where the transition function and cost functions are additively separable: c(x,u)=c1(x)+c2(u) and x’=f1(x)+f2(u) + w (Assumptions 3.1). Furthermore, f1(x) is Lipschitz continuous, f2(u) is linear, c1(x) is convex and Lipschitz continuous, and c2(u) is linear in u. The disturbance w has a finite support (Assumption 2.1). The state space for x and decision space for u are continuous. Thus, the authors consider problems such that [TJ](x) = c1(x) + min_u [c2(u) + gamma sum_i  p_i J(f1(x)+Bu+w_i)]. A problem that fits this description is the stabilization of an inverted pendulum with discretized disturbances, studied in Section 4. With this choice of assumptions, and assuming the value function is convex (which holds true if f1(x) is linear or linearized, that is, if x’=Ax+Bu+w), convex duality can be applied to the minimization problem over (u,x”) given x and subject to x”=Ax+Bu, which gives another representation of the optimization problem, based on the convex conjugate of c1 and the convex conjugate of e(x”)=gamma E J(x”+w).

The authors propose and study an algorithm that relies on computing these convex conjugate functions numerically in order to provide an alternative way to the computation of the value function J. They establish error bounds (Theorem 3.13) in terms of theoretical quantities of the problem data.
main_review: The results appear to be new. While dualization is a classical concept in optimization, and there is preliminary work on applying these ideas to deterministic systems, the extension to stochastic systems and the results on error bounds appear to be new.
The work is technically sound given the assumptions. Matlab codes are provided. In the opinion of this reviewer, the limitations of the work are
(i) the scope of problems that can be treated by the proposed approach, compared to classical VI. For instance, the authors state that the curse of dimensionality from classical VI has exponential rate m+n, while their method has exponential rate max(m,n). But classical VI does not rely on a convex value function assumption that restrict the admissible class of transition and cost functions. The test problem presented in the numerical section does not itself satisfy all the assumptions assumed by the theory (as pointed out by line 463 of the extended manuscript).
(ii) the practicality of the bounds, compared to classical VI. The error bounds of the proposed approach do not seem to easily lead to a stopping criterion as they rely non-universal constants and quantities that seem difficult to evaluate or bound. 
(iii) it is not clear if the assumption that the transition function is linear to ensure convexity of the value function and fully justify a dualization approach is needed for the approach to be sound. The numerical examples provided actually use a system where control techniques using a linearization of the transition function are known to work well. 
(iv) the fundamental reason that would explain that solving in the dual space is easier than solving in the primal space is not fully apparent. The test problem has a unidimensional decision variable, so it is difficult to draw strong conclusions on scaling from there. 
The submission is clearly written. The results are significant, although they seem to be most relevant for certain classes of control problems that are already well solved (it is hard from the current manuscript to identify problems that would significantly gain from the new approach).

limitations_and_societal_impact: The contributions are essentially mathematical. The work does not appear to have potential negative societal impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper presents a fast method for solving certain classes of optimal control problems, by implementing a value iteration (VI) algorithm that takes advantage of convex duality. 
The basic idea is to take advantage of the fact that for two functions $f_1, f_2$, we have $(f_1 \square f_2)^* = f_1^* + f_2^*$, where $f^*$ denotes the Legendre-Fenchel transform of $f$, and $(f_1 \square f_2)(x) = \inf \\{f_1(x_1) + f_2(x_2) : x_1 + x_2 = x \\} $ denotes the infimal convolution of $f_1, f_2$.
Thus, the slow $\inf$ operation can be replaced with a fast addition operation.
The paper provides analyses of the convergence, time complexity, and error of the algorithm.
When compared to a "naive" VI algorithm in which each iteration takes $O(X U)$ (where $X$, $U$ are the grid sizes of the state and input spaces, respectively), the algorithm presented in this paper can achieve $O(X+U)$.
Finally, the paper provides a numerical example implemented in MATLAB.
main_review: This paper presents an fast algorithm that is probably novel to most researchers and practitioners who need to solve optimal control problems.
The ideas first appeared in Bellman & Karush (1962), and the algorithm was most recently presented and analyzed in Kolarijani and Esfahani (2020). 
The latter paper applied the algorithm to finite-horizon optimal control problems with deterministic input-affine dynamics, and provided detailed analyses of the algorithm's time complexity and error properties.
This current paper goes beyond that paper in applying the algorithm to discounted, infinite-horizon problems with stochastic dynamics.
The marginal contribution of this paper is incremental; however, the novelty and performance of the algorithm may be of interest to researchers who need to solve problems that fall within the class handled by this algorithm.

The paper is well-written, clear and concise. The mathematical details seem correct (though I did not check them closely). I have addressed some limitations of the paper in the "Limitations" section below.

Overall, the paper is interesting and presents a novel algorithm with the potential for large performance gains in solving optimal control problems. The applicability of the algorithm to more complicated, real-world problems could be an interesting and useful research question.

Bellman and Karush (1962). Mathematical programming and the maximum transform. Journal
of the Society for Industrial and Applied Mathematics, 10(3):550-567.  

Kolarijani and Esfahani (2020). Fast approximate dynamic programming for input-affine
409 dynamics. preprint arXiv:2008.10362, 2020.
limitations_and_societal_impact: Limitations

1) The paper clearly states the restriction on the class of problems that the algorithm applies to: principally, the stage cost function $C(x, u)$ must be jointly convex.
The baseline comparison algorithm is a naive version of VI. 
A single iteration of VI must solve the Bellman equation
$$
  J(x) = \min_u \\{ C(x, u) + \gamma E\[ J(g(x, u, w) \] \\}
$$
If $X, U$ are the grid sizes of the state space and input space, respectively, then a brute-force implementation will search through every possible $u$ for every possible grid point value of $x$, giving $O(X U)$ time complexity.
However, since it is assumed that $C(x,u)$ is convex, it is not hard to show that the value function $J$ must also be convex, and thus faster optimization algorithms that use gradient information can be used.
Comparing the performance of CVI against a gradient-aware algorithm would provide a more realistic comparison for the speed advantage of CVI.


2) The numerical example provided is a two-dimensional noisy inverted pendulum, which may be too simplistic to provide an indication of the potential strengths and weaknesses of the algorithm.
It would be useful to see how the algorithm handles more complicated problems, and how some practical issues in implementing the algorithm are addressed.
For example, when constructing the approximate Legendre-Fenchel transform $f^*$, the grid space of $f^*$ must be large enough to encompass the full range of slopes of the primal function $f$.
For certain functions, this range may be very large, extending to infinity (e.g. $\log(x)$ or $x^{-\alpha}$).
Especially in higher dimensions, it is non-trivial to construct an approximation for $f^*$ that encompasses such a large range while maintaining accuracy.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies the problem of dynamic programming with continuous state and action spaces. 
The authors first propose the VI which naively discretizes the state and action space and performs the classical value iteration. The authors use this method as a baseline for comparison with CVI developed in this paper. 
Regarding the CVI, this algorithm performs VI in the the conjugate domain. In particular, by taking the dual of the objective function, we take the problem to the dual space. By doing so, instead of taking minimum over all the actions, the problem is reduced to a summation. Hence, the complexity of the CVI is better than the VI in the order of the cardinality of the action space.
main_review: - Since the J function can be bounded above by O(1/(1-gamma)), I do not understand the purpose of the Theorem 3.11. Isn't it result in a trivial bound?
- Comparison in the experimental result is not sufficient. For instance, can the authors compare the performance of their algorithm with the ones in [8] and [22]? Specifically section 8.1 in [22] that talks about aggregation techniques to deal with the curse of dimensionality, and references in section 8.1 in the book. Also look at table 4.4 in [22] for a variety of the references to compare with. 
- There is no Assumption 3.7-(ii), there is no Fig 1-d.
limitations_and_societal_impact: - Lack of comparison with the related works.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper proposed a new value iteration algorithm (CVI) for optimal control of stochastic system with continuous state space. The proposed algorithm discretizes the state space and performs the value iteration step in the "conjugate domain" to reduce one-step computational complexity. It was shown the proposed algorithm converges under conditions on the stochastic system, discretization, and etc. The proposed algorithm CVI, its variant CVI-d are compared to classical value iteration (VI) over a noisy inverted pendulum experiment.
main_review: The paper is well written and the language is precise.

The main benefit of the propose algorithm is the reduced per-step complexity (Thm 3.10). However, no guarantees on how many iterations will be needed for the algorithm to stop (see Alg.1 line 4) given the error tolerance parameter e_t in Algo 1. Therefore, Thm 3.10 along with Thm 3.11 cannot really justify the claim of "fast approximate dynamic programming". More on this point in the experiment part below.

I understand, in the inverted pendulum experiment, the CVI algorithm needs less iteration than VI, but we need more evidence to be convinced this is a fast value iteration algorithm. The experiment also brings another question, Fig.1 c shows the resulting greedy policy learned from CVI is worse than classic VI in all state grid settings; it is much worse with coarse grids. The variant of CVI, CIV-d (with dynamic grid in dual space), was able to find better policies, but there is no guarantee for that.

For originality, I am not very familiar with literature in this area (sample based value iteration). It will help a lot if the authors clarify the technical contributions of the current algorithm compared to d-CDP from [18, reference from the paper]. Since the authors claim that the current algorithm extends d-CDP from infinite-horizon, discounted cost to stochastic dynamics.
limitations_and_societal_impact: See the main comments above.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper develops an approximate value iteration method for an infinite-horizon, discounted-cost Markov Decision Processes (MDPs) that satisfy a given set of regulatory assumptions. The idea is to work on a dual space that replaces the DP value function by a reformulation written in terms of biconjugate operations. The authors present an algorithm that applies the conjugate operators iteratively, and present convergence and other structural results associated with the resulting errors. Numerical results compare the proposed approach against a traditional value iteration and a variant that generated dynamic discretization grids.
main_review: **Originality**

The paper is an extension the previous work by Kolarijani and Esfahani (2020), which lays out the fundamental ideas underlying conjugate dual operators in MDPs and has similar error-type analysis. The key contribution of this paper is that it extends those ideas in different ways, incorporating stochastic dynamics (more briefly discussed in that paper) and involves a more general class of MDPs (e.g., infinite-horizon and resulting numerical approximations). 

While such extensions are no doubt a challenging and admirable endeavor, their contribution is much more technical and builds upon the novelty of that previous work. Assuming the previous work is a separate publication and the current one does not encompass that one, my concern is that the originality of this paper is more restricted to an MDP audience, given the (usual) wide array of assumptions that must be in place for this approach to be applicable. 

**Quality** and **Clarity**

The paper is excellently well written and rigorous. It is, however, quite dense to read: some concepts I was only able to grasp after reading the "extended manuscript" in the supplemental material, which includes more examples (I appreciate the authors for that). Nonetheless, it is overall a very pleasant and fluid read. There are also six pages of technical proofs, some involved but most using standard contraction and similar operations - I did my best to verify them and they seem correct. 


**Significance**

As mentioned before, my major concern is that the paper seems to be more suitable to a more specialized audience of NeurIPS due to its strong technical aspects. The numerical simulations are very limited, and in my view are not very effective in demonstrating the practical relevance of their new approach.

However, the paper reads very well and the conjugate reformulation is a relevant (and impactful) contribution. It does reduce the VI complexity significantly and can be of potential use in different dynamic programming models. 

**Questions and Minor Points** 

- How restrictive is assumption 3.1-(ii)?
- In Assumption 3.5: "feasibile" --> "feasible"
limitations_and_societal_impact: The paper indeed lacks a discussion of the limitations of their methodology. In particular, authors could be clearer with respect to trade-offs of the conjugate formulation and the traditional VI algorithm.
review_title: null

Meta-review: The paper suggests a fast method for solving a class of optimal control problems by introducing a variant of the Value Iteration (VI) algorithm that benefits from the convex conjugate transform. This improves the computational complexity of solving each step of VI from O(|X||U|) to O(|X| + |U|).

Most reviewers are positive about this work. One of the reviewers (mb6w) is on the negative side, but I believe their concerns and questions are adequately answered (the reviewer did not acknowledge the authors' response). Therefore, I would recommend acceptance of this paper.

I would encourage the authors to incorporate reviewers' comments and suggestions in order to improve their paper. Some of improvements can be along the followings:

- Emphasizing more how this work can be relevant to NeurIPS community, as this paper is different from a typical paper on MDP or RL appearing at NeurIPS (no focus on learning; focusing on a special class of problems, etc.)
- Clarifying and emphasizing the technical contributions of this work compared to [18].
- Including larger-scale experiments.

I would also note that the acronym of CVI has already been used in the context of Value Iteration:
*Conservative Value Iteration* (Kozuno, Uchibe, Donya, "Theoretical Analysis of Efficiency and Robustness of Softmax and Gap-Increasing Operators in Reinforcement Learning," AISTATS, 2019) and *Characteristic Value Iteration* (Farahmand, "Value Function in Frequency Domain and the Characteristic Value Iteration Algorithm," NeurIPS, 2019), so the authors may want to use another acronym to reduce possible confusion. There is no need to cite these work, as they are not related enough.
Decision: Accept (Poster)