Venue: NeurIPS 2022 Conference

Reviews:

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 proposes a method for learning the probabilities of the transitions a Markov Decision Process from observed data. The method assumes that the structure of the MDP is available to it. It initializes these probabilities to a wide interval, and then as data keeps arriving, the probability is updated. Based on the learned probabilities, the authors compute an optimal policy, and learning stops once the optimal policy rewards reach a certain threshold (or may be stopped by the user after a certain amount of data is gathered).
strengths_and_weaknesses: The paper is clearly written for the most part. The computation of the P_MinMax was not shown in the paper, but I am assuming this was already described in the papers cited.

The algorithm is a rather straightforward generalization of estimating a probability from sample data --- given a stream of 0, 1 values, what is a good interval bound for the probability? The authors propose either using Hoeffding's inequality, or a variant of Laplace smoothing. It would be good to understand how the MDP structure helps in getting these estimates quickly, as of now it seemed that the different transitions were treated independently.
questions: Page 3: The specification of P_MaxMin assumes that the MDP is chosen from the possible MDPs and the best policy is chosen for it. How is the MDP chosen --- is it assumed that the MDP is chosen so that the best policy for it will produce the smallest reward?

Page 6: It was not clear to me how to initialize prior strength interval n_i. You said that they can be chosen arbitrarily, so one choice could be [0,0]. But this would violate Proposition 2 --- if P_i = (e, 1-e), then if N = 1, k_i = 0, then P'_i = (0,0). There was no proof in Appendix B.
limitations: Not applicable.
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 considers the problem of learning an (over) approximation Markov Decision Process (MDP) in the form of a uncertain Markov Decision Processes (uMDP). This model is then used synthesizing a policy that is robust to the inferred uncertainty in the transition probabilities. The is done as an iterative process: (i) A uMDP is conjectured. (ii) An (optimistic) exploration policy is synthesized (iii) The transition probability intervals are updated based on the newly collected data. This update is either done using a PAC estimate on the interval or a form of weighted updating of the bounds (called linear updating). The paper ends by comparing against a MAP base-line and an established robust RL algorithm.
strengths_and_weaknesses: # Strengths
1. The problem is well motivated and of interest to this venue.
1. The approach builds off of well established theoretical machinery and combines them in a well motivated way.
1. The baselines and metrics seem reasonable and help illustrate the strength of the approach.

# Weaknesses
1. (minor) In the formal verification community, this model is also sometimes know Interval Markov Decision Process. It would have been helpful early on to mention this.
1. Need to know a-priori which transitions are impossible. This seems reasonable in many domains, but limits the applicability.
1. Unclear how this approach scales to very large state and action spaces. 
1. Arguably an incremental result that builds on well established machinery.
1. (minor) Does not easily detect that there has been a distribution shift (change of environment). This is left as future work.
1. **(primary concern)** I did not understand how the PAC bound was used iteratively. Doesn't Hoeffding's result require i.i.d. sampling? This is violated by changing the exploration policy right? This is my primary hesitation in assigning a higher score.


questions: 1. How is the PAC result employed given the distribution shift? Is this update procedure not iterative?
1. Can the minimal transition probability $\epsilon$ be made symbolic, e.g. in infinitesimal ? In particular, it feels like one could easily detect if $\epsilon$ should have been made smaller since its only used to clip the probability distributions right?
1. Aside from capturing model uncertainty, another application of interval MDPs is as a form of model compression. Is there a path for making the approach work in such settings, i.e., trade-off resolution for a smaller (easier to train) model?
limitations: - Limited to finite MDPs where the graph is already known. This is often satisfied, but there are interesting domains, e.g., continuous, where this does not hold.
- Not as fast as robust RL baseline at adapting to distribution shift. This is understandable and listed as future 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: The paper develops an anytime-learning technique to estimate the transition probabilities of a Markov Decision Process (MDP). Given an MDP with a known transition graph, the methodology begins by calculating the worst-case performance of a policy $\pi$ with respect to an uncertain MDP (uMDP) and an associated temporal-logic specification.  If such a policy violates the desired threshold, the authors sample a trajectory and update the uncertainty set according to either Hoeffding's inequality or linearly updating intervals. Numerical results evaluate the approach with respect to performance and estimation/model errors. 
strengths_and_weaknesses: Strengths
- Innovative robust perspective to learn transition probabilities
- Excellent exposition

Weaknesses
- Lack of theoretical insights
- Limited numerical analysis

Major Comments

Overall, the paper is rigorous and excellently well written; it was very enjoyable to read, with all steps clearly motivated and outlined. I found the idea to be innovative as typically probability estimations in MDPs are limited to MAP-based approaches, and there is a clear methodological contribution provided by the "robust" view that the authors offer. However, perhaps due to its "proof of concept" aspect, the paper tends to be much more on the computational side and lacks a more in-depth analysis of the approach, in my personal view. More precisely:

(i) [Theory.]  It was not clear to me why this method would ever be (rigorously) effective. Specifically, the authors mention that the learning is "conservative" due to the robust nature of the worst-case policy evaluation. While the numerical results are promising, there are few theoretical insights on how conservative it could be. Is there any particular MDP structure (e.g., in the transition probabilities or transition graph) that the policy would be optimal, i.e., the transition probabilities match the ground truth? Or, conversely, could it be arbitrarily poor, and when does that happen? What was special about the instances tested for the good performance that was observed? 

Perhaps my primary concern is that there is little indication of the overall performance of this approach, and the tradeoffs associated with the robust view, which for me is one of the key (and interesting) contributions of the work. 

(ii) [Numerical Analysis.] My impression is that the numerical results and the choice of environments were well carried out and sufficiently diverse. However, it would benefit from a more thorough analysis and intuition on why some of the behaviour was observed. First, why would LUI and PAC be roughly equivalent? Does that mean the method is less sensitive to the Bayesian updates that are performed? Second, results on the "Chain" environment are very interesting; I wonder why LUI/PAC are choosing the bad actions; perhaps that can relate to point (i) above? Overall, the paper is missing a more careful discussion to understand when the proposed methods work best or can be outperformed by reinforcement learning / MAP techniques.

Minor Note
- Proof *of* Proposition 1








questions: 1. Are there any insights/examples that illustrate when the approach leads to optimal policies? And poor policies?

2. When would LUI be preferable to PAC? While this was discussed briefly, I feel that some clarifications could be extremely helpful. 
limitations: N/A
review_title: null

Meta-review: metareview: The paper makes a good algorithmic contribution and provides its theoretical analysis. It would benefit from a more extensive empirical evaluation, for instance, evaluating on IPPC-style MDPs expressed in PDDL and RDDL and on MDPs with high-dimensional observations (block MDPs), but even as is this work is a solid step forward.  
confidence: Less certain
Decision: Accept