Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper provides a Bayesian risk Markov Decision Process (BR-MDP) formulation to address parameter uncertainty in MDP. 
- The paper uses a Bayesian posterior distribution as opposed to ambiguity set, and imposes a risk functional on the objective function with respect to the posterior distribution. 
- Specifically, the authors assume the distribution of the randomness in the system belongs to some parametric family, and model the uncertainty over the unknown parameters via Bayesian posterior distributions. 
- Furthermore, a CVaR risk functional taken with respect to the posterior distribution on the expected total cost is proposed in a nested form to promote time-consistency solutions.
- Finally, the authors derived a dynamic programming solution with an augmented state that incorporates the posterior information and proposes an analytical approximate solution to BR-MDP. 
strengths_and_weaknesses: ## Strength
- The idea of using Bayesian posterior to model the uncertainty in the parameters of MDP is intuitive and will improve the overly conservative problem in distributionally robust-MDP method. 
- Compressive theoretical analysis of the approximation are provided. 
- The proposed approximation method reduce the computation time significantly while not influencing the performance. 


## Weakness:
- The readability of the paper suffers from inconsistency and heavy notations. 
- The paper seems unfinished since it lacks a conclusion section. 
- The effectiveness of the paper is only evaluated on simple synthetic experiments. 
questions: - Section 3.2, The first paragraph is hard to follow, the rewriting of equation 6 is not clear. 
- Line 233, it says $V_t(s_t, \mu_t)$  stands for the "optimal" value function, what does  $V^*_t(s_t, \mu_t)$ (equation 6) stand for? 
- Does the proposed method scale when the parameter space is high-dimensional? 


Possible typos: 
- Equation 6: rhs, $V_{t+1}^*(s_{t+1}, \mu_t)$ should be $V_{t+1}^*(s_{t+1}, \mu_{t+1})$
- Line 234-235, both $f(\epsilon; \theta)$ and $f(\epsilon|\theta)$ appeared in this equation. Do they mean the same thing? 
limitations: The authors did not addressed any limitations and potential negative societal impact of their work. 


## Suggestions: 
###  Several ways to improve the clarity of the paper: 
  - Condense introduction part (the current version may well suited for a journal paper; but for conference paper, the space of the introduction is a bit too much) 
  - Check the notations and remove redundant information. e.g. equation 4 appears in multiple places (line 177, line 213 (integral is replaced by \Sum).
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: The paper presents a Bayesian risk approach for finite-horizon MDPs under uncertainty. By using some techniques from Bayesian risk optimization, the authors develop an approximation algorithm to solve the MDP problem. The algorithm is then supported by numerical experiments based on two finite-horizon offline planning problems.  The paper is well-written. Both robust MDP and Bayesian risk optimization are important areas in Machine Learning/Optimization. Thus, the problem considered is interesting and worth investigating. 
strengths_and_weaknesses: ## Strengths:
The formulation is new.  The paper is technically sound and well written/organized. 
The combination of MDP under uncertainty and Bayesian Risk Optimization seems interesting and promising. 

## Weaknesses:
 I believe the paper is not ready for publication due to several limitations as stated below:

Robust MDP and Bayesian risk optimization formulations are widely studied and well understood. Thus, the results developed in the paper are quite **trivial**, given all the techniques we have in the literature. For example, Section 2 (including Algorithm1) only presents already known or trivial material. The alpha-function representation is also a direct result of equation (5) and some techniques in the Bayesian risk optimization literature. The Bellman equation in (6) is just a standard Bellman equation with a continuous state space, for which several efficient (approximation) algorithms exist, but I do not see an explicit comparison of the proposed algorithm against existing ones.  

The paper only focuses on finite-horizon MPDs which makes it limited, as many applications will require infinite MDPs

Some assumptions are vague and require explanations, for example, the authors assume on Page 5 that \Theta is finite. It is true that we can always discretize a continuous space, but it raises several questions: How to discretize, how many discrete samples would be needed?  approximation errors as a function of the discretization points...

The authors claim that their algorithm can be extended easily to other coherent risk measures. To support this point, it is better to provide formulations and results with other risk measures.
questions: - Page 4, line 2 is unclear, what is $\Xi_t$. It was not defined before
- The pdf and the version in the supplement are different. Any explanation for this? 
- Why is the conclusion missing?
- In (6), both $V_{1}$  and $V_{t+1}$ on the both sides depend on $\mu_t$. Should it be $\mu_{t+1}$ on the right hand side?
limitations: There would be no potential negative societal impact of this work.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper proposes a Bayesian risk MDP called BR-MDP to account for both the uncertainties in transition probabilities and costs/rewards. The model takes a nested form of the risk functional, which endows its optimal policy with time consistency. The computational difficulties in the expectation and the risk functional, as well as the posterior with a possibly infinite dimension, are two main challenges in obtaining the solution of the BR-MDP. To overcome the latter, the authors focus on the conjugate families of distributions, while for the former, the authors consider the conditional value-at-risk and derive an $\alpha$-function approximation of the optimal value function and propose an algorithm to solve for the approximate value function efficiently. Two empirical studies are carried out to demonstrate the performance of the proposed model and the efficiency of the proposed algorithm.
strengths_and_weaknesses: Strengths: 
Overall, the paper is well-written. I especially appreciate the design of the approximate dynamic programming to overcome computational inefficiency. 

Weaknesses:
1. Please be very specific if the proposed framework only works with one-dimensional uncertainty, i.e., $\theta$. If yes, please acknowledge this well and provide strong justifications. 
2. I think several key assumptions for the whole framework should be listed more clearly and frankly. For example, when talking about the $\alpha$-function representation (a major focus of this paper), the authors hide the critical assumption that "the parameter space is a finite set" quite "deep", which does not seem to be proper to me. For another example, for Theorem 3.2, the authors require joint convexity while not providing any justification (e.g., is it easy to satisfy). 
3. I would encourage the authors to talk more about how they are motivated by "POMDP" and discuss the connections in more detail.
4. In the experiments, the results are not convincing enough (\textit{e.g.}, only one sample size is considered, and the advantage of the proposed model is not obvious,
questions: 
Below are some other comments for the paper.

$\bullet$ Line $138$, page $4$ (Section $2$): I wonder what is the meaning of $\Xi_t$. Is it a random variable or a set?

$\bullet$ Line $164$, page $4$ (Section $2$): by "To illustrate", I expect the authors to demonstrate the time consistency of the BR-MDP, but they just show that the objective value of BR-MDP serves as an upper bound for the objective of the one considering static risk functional. I would suggest the authors relate this to the concept of time consistency.

$\bullet$ Line $166$, page $4$ (Section $2$): based on formula $(2)$, should it be $\mathcal{C}_1(s_1)$ rather than $\mathcal{C}_1(s_1,a_1,\xi_1)$?

$\bullet$ Line $212$, page $6$ (Section $3$): the definition $\Gamma_t=\{\alpha_t\}_{a_t\in\mathcal{A}}$ is confusing. Does it imply that the cardinalities of $\Gamma_0, \Gamma_1,...$ are all $\vert\mathcal{A}\vert$?

$\bullet$ Line $294$, page $8$ (Section $4$): what is the value of $M_C$?

$\bullet$ Lines $312$ to $313$, page $8$ (Section $4$): it seems to me that the low variation of performances of a model is always desirable.

$\bullet$ Lines $334$ to $337$, page $9$ (Section $4$): the advantage of BR-MDP over DR-MDP in Table $1$ is too minor (59.64(1.42) versus 60.00(0.00)). Hence this may not be an ``evident illustration".

$\bullet$ Line $342$, page $9$ (Section $4$): to better illustrate the claim that "the difference is small", I would suggest the authors provide a table to report the relative gaps (in \%) between $\tilde{V}^*_0(s_0,\mu_0)$ and $V^*_0(s_0,\mu_0)$.

$\bullet$ Could the authors briefly clarify why the exact solution of CVaR BR-MDP is computationally available in the experiments (Since they state in the first paragraph of Section $3$ that this exact solution is hard to obtain)?

$\bullet$ The sizes of the historical data are fixed to be $10$ in both experiments. I would suggest the authors vary the sample sizes to better examine the performances of the models.

$\bullet$ Could the authors explain why the computation times of "Nominal" and "DR-MDP" are not reported in Table $1$?

$\bullet$ I would suggest the authors explain why the performances of DR-MDP are not reported in Figure $1{\rm a}$.

$\bullet$ Line $121$, page $3$ (Section $2$): "$Z$" should be "$X$"?

$\bullet$ Lines $169$ to $170$, page $4$ (Section $2$): the right-hand side of the inequality, should it be $\mathbb{E}_{\xi_1}$ rather than $\mathbb{E}_{\xi_1\vert\xi_0}$ (based on the independence of $\xi_t$'s described in Lines $135$ to $136$)?

$\bullet$ Lines $205$ to $206$, page $5$ (Section $2$): should it be "...$V_{t+1}^*(s_{t+1},\mu_{t+1})...$"?

$\bullet$ Lines $211$ to $213$, page $6$ (Section $3$): the statement should be: "$V_t^*=...$, where $\alpha_t(s_t,\theta)=...$". Also, what is the range of $t$ for the equations to hold?

$\bullet$ Lines $234$ to $235$, page $6$ (Section $3$): $f(\xi\vert\theta)$ should be $f(\xi;\theta)$ for consistency.

$\bullet$ Algorithm $2$, page $7$: the algorithm should have only one "\textbf{output}".

$\bullet$ Table $1$, page $9$ (Section $4$): the rows of the two tables should be aligned correspondingly.

$\bullet$ Figure $1$, page $9$ (Section $4$): it might be better to divide Figure $1$ into two figures.


limitations: Yes
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper proposes the Bayesian Risk MDP (BR-MDP) framework to deal with the epistemic uncertainty in sequential decision problems. In the introduced framework, a coherent risk functional is applied to the expectation of the total cost under the posterior distribution of the model parameters. Differently from prior works, the risk functional is applied in a nested form, which preserves the time consistency of the objective and allows to write a dynamic programming equation of the optimal value function. However, solving the dynamic programming problem analytically is far-fetched. The paper thus introduces an approximate algorithm, partially inspired by POMDP methods, for a specific instance of the BR-MDP with the CVaR risk functional. Finally, the given methodology is empirically evaluated in toy domains.
strengths_and_weaknesses: Strengths
- (Relevant Problem) This paper tackles the relevant problem of robust decision-making under uncertainty on the model parameters.
- (Framework) I am not particularly familiar with the related literature, but to my understanding this is the first Bayes-adaptive framework that incorporates a time consistent risk measure over the epistemic uncertainty.
- (Methodology) Since solving the BR-MDP problem is intractable in general, the paper proposes an interesting value function approximation method that is partially inspired by POMDP literature.

Weaknesses
- (Weak Empirical Analysis) The empirical analysis does not fully motivate the framework and the methodology, as the performance of the proposed approach does not seem to be significantly superior than the (not necessarily strong) baselines.
- (Notation and Clarity) The notation is quite convoluted and not always sharp. This undermines the clarity of some portions of the work.

The premise of incorporating the sensitivity to the epistemic risk in a Bayes-adaptive framework is interesting, and also a natural continuation of the robust decision-making stream of works. The technical contribution does not seem to be ground-breaking, as most of the ideas can be traced back to previous works in cost-variability sensitivity and POMDPs, but this would be totally fine given the other contributions, i.e., the methodology and the framework itself. My main concern regards the empirical validation: It is ok for an essentially methodological/theoretical paper to have an empirical analysis in toy problems, but it should showcase the benefit brought by the method. Instead, the performance seems to be close to the baselines, especially to the naïve maximum likelihood estimator.

For the aforementioned reasons, I am still unsure on the significance of the work, and I am providing a slightly negative evaluation. However, I am open to increase my score if the authors can address my concerns on the motivation and potential of the proposed approach in their rebuttal.

---
AFTER DISCUSSION

I have increased my score to weak accept to acknowledge the value of this work that emerged from discussion with the authors and other reviewers. However, I believe this paper is still missing either a stronger theoretical result on the benefit of the nested form or a stronger empirical evaluation in more challenging domains to be outstanding in any way.

questions: 1) The work by Chow et al., 2015 [22] seems to be closely related to this submission. Although they tackle the cost-variability risk instead of the epistemic risk, they also consider a CVaR risk measure in a nested form to derive a Bellman equation (Sec. 3) that allows for approximate dynamic programming. Can the authors discuss the relation with this prior work, and especially the technical differences with respect to this submission?

2) Chow et al., 2015 [22] make an interesting connection between cost-variability risk and epistemic risk. They prove that a solution that is sensitive to the cost-variability provides also robustness to the epistemic uncertainty as a by-product. Do the authors think that a similar case could be made in their setting, i.e., that a solution to the BR-MDP problem could provide some robustness to the cost-variability risk as well?

3) The proposed BR-MDP framework is similar in flavor to a Bayes-adaptive approach with a time consistent risk functional over the model parameters. Can the authors discuss the impact of the time consistency? Can they explain why an approximate solution to the BR-MDP problem is necessarily better than a (possibly exact) solution to the BAMDP problem with a risk functional applied on the full trajectory rather than in a nested form?

4) Is the proposed approximate methodology really practical? Can the authors comment on how the Eq. 8 could be computed/estimated in more challenging domains?

5) Can the authors better explain why the Eq. 7 is significantly easier to compute than the exact Eq. 6? I guess the main benefit is pulling the min out of the expectation, but I found this paragraph quite hard to process (especially lines 218-222 could be revised).

6) Theorem 3.4 characterizes the approximate value function as an upper bound of the exact value. Do the authors believe there is hope to assess guarantees on the gap between the two?
limitations: I think that a discussion on the negative societal impact can be avoided in this paper. However, the authors answered 'Yes' to the checklist question on the limitations of their work, but they did not provide motivation or context for their answer. Can the authors list the main limitations of their approach?
review_title: null

Meta-review: metareview: Motivated by the often overly conservative characteristics of distributionally robust MDPs, this paper employs (nested) Bayesian posterior distributions to model the uncertainty over MDP parameters. The programming solution is similar to belief state approximation methods for POMDPs. The experiments (after revision) seem to demonstrate the advantages of this approach. The reviewers believe the paper could be improved with better theoretical analyses and/or more compelling experiments (higher dimensional tasks in particular). The paper lacks a strong advocate among the reviewers, but their aggregate sentiment is that it is worth accepting to the conference unless there are other more deserving works that it would displace.
confidence: Less certain
Decision: Accept