Robust Anytime Learning of Markov Decision Processes
Authors: Marnix Suilen
Thiago D. Simão
David Parker
Nils Jansen
Venue: NeurIPS 2022 Accept (2022)
Keywords: Markov Decision Process
Robust Reinforcement Learning
Model-based Reinforcement Learning
Formal Verification

Abstract: Markov decision processes (MDPs) are formal models commonly used in sequential decision-making. 
MDPs capture the stochasticity that may arise, for instance, from imprecise actuators via probabilities in the transition function. 
However, in data-driven applications, deriving precise probabilities from (limited) data introduces statistical errors that may lead to unexpected or undesirable outcomes.
Uncertain MDPs (uMDPs) do not require precise probabilities but instead use so-called uncertainty sets in the transitions, accounting for such limited data.
Tools from the formal verification community efficiently compute robust policies that provably adhere to formal specifications, like safety constraints, under the worst-case instance in the uncertainty set. 
We continuously learn the transition probabilities of an MDP in a robust anytime-learning approach that combines a dedicated Bayesian inference scheme with the computation of robust policies. In particular, our method (1) approximates probabilities as intervals, (2) adapts to new data that may be inconsistent with an intermediate model, and (3) may be stopped at any time to compute a robust policy on the uMDP that faithfully captures the data so far. 
Furthermore, our method is capable of adapting to changes in the environment. 
We show the effectiveness of our approach and compare it to robust policies computed on uMDPs learned by the UCRL2 reinforcement learning algorithm in an experimental evaluation on several benchmarks.

Robust Anytime Learning of Markov Decision Processes
Marnix Suilen
Thiago D. Simão
Department of Software Science Radboud University Nijmegen, The Netherlands
Department of Software Science Radboud University Nijmegen, The Netherlands
David Parker
Nils Jansen
Department Computer Science
Department of Software Science Radboud University Nijmegen, The Netherlands
University of Oxford Oxford, United Kingdom
Abstract
Markov decision processes (MDPs) are formal models commonly used in sequen- tial decision-making. MDPs capture the stochasticity that may arise, for instance, from imprecise actuators via probabilities in the transition function. However, in data-driven applications, deriving precise probabilities from (limited) data in- troduces statistical emrors that may lead to unexpected or undesirable outcomes. Uncertain MDPs (uMDPs) do not require precise probabilities but instead use so-called uncertainty sets in the transitions, accounting for such limited data. Tools from the formal verification community efficiently compute robust policies that provably adhere to formal specifications, like safety constraints, under the worst-case instance in the uncertainty set. We continuously learn the transition probabilities of an MDP in a robust anytime-leamiing approach that combines dedicated Bayesian inference scheme with the computation of robust policies. In particular, our method (1) approximates probabilities as intervals, (2) adapts new data that may be inconsistent with an intermediate model, and (3) may be stopped at any time to compute a robust policy on the uMDP that faithfully captures the data far. Furthermore, our method is capable of adapting changes in the environment. We show the effectiveness of our approach and compare it to robust policies computed on uMDPs learned by the UCRL2 reinforcement learning algorithm in an experimental evaluation on several benchmarks.
Introduction
Sequential decision-making in realistic scenarios is inherently subject to uncertainty, commonly captured via probabilities. Markov decision processes (MDPs) are the standard model to reason about such deecisio-mmaiin problems [Puterman 1994 Bertsekas 2005). Safety-critical scenarios require assessments of correctness which can, for instance, be described by temporal logic [Pnueli] 1977 or expected reward specifications. A fundamental requirement for providing such correctness guarantees on MDPs is that probabilities are precisely given. Methods such variants of model- based reinforeement learning [Moerland et al. 2020) PAC-learning [Strehl al.) 2009) can learn MDPs by deriving point estimates of probabilities from data to satisfy this requirement. This
Supported by NWO OCENW.KLEIN, 187: "Provably Correct Policies for Uncertain Partially Observable Markov Decision Processes", NWA. 160. 18. 88.288 (Prima Vera) and by the ERC under the European Union's Horizon 2020 research and innovation programme (FUN2MODEL, grant agreement No. 834115).
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

derivation naturally carries the risk of statistical errors. Optimal policies are highly sensitive to small perturbations in transition probabilities, leading to sub-optimal outcomes such as a deterioration in performance [aannrr et al. 2007 Goyal and Grand-Clement 2020]
Uncertain MDPs (uMDPs;; also known interval robust MDPs) extend MDPs incorporate such statistical errors by introducing an additional layer of uncertainty via uncertainty sets on the transition
function NNlii and Ghaoui 2005 Wiesemann al. 2013 Goyal and Grand- Clement 2020 Rigter et al. 2. The solution of a uMDP is a robust policy that allows an adversarial selection (i.e., the
cosst-case scenario) of probabilities within the uncertainty set, and induces worst-case performance (a conservative bound on, e.g., the reachability probability or expected reward). The problem of computing such robust policies, also called robust verification, is solved using value iteration or convex optimization, where the uncertainty sets are convex (Wolif et al. 2012 Puggelli et al., 2013).
Our approach. We study the problem of learning MDP from data. We propose iterative learning method which uses uMDPs as intermediate models and is able to adapt to new data which may be inconsistent with prior assumptions. Furthermore, the method is task-aware in the sense that the learning procedure respects temporal logic specifications. In particular, our method learns intervals of probabilities for individual transitions. This Bayesian anytime-learning approach employs intervals with linearly updating conjugate priors [Walter and Augustin| 2009], and can iteratively improve upon uMMP that approximates the true MDP we wish to learn. This method not only decreases the size of each interval, but may also increase it again in case of so-called prior-data conffict where new data suggests the actual probability lies outside the current interval. Consequently, a newly learned interval does not need to be subset of its prior interval. This property makes our method especially suitable to learn MDPs where the transition probabilities change. Alternatively, we also include probably approximately correct (PAC) intervals via Hoeffding's ' inequality (Hoeffding] 1963), which introduces a correctness guarantee for each transition.
We summarize the key features of our learning method, and what sets it apart from other methods.
An anytime approach. The ability to iteratively update intervals that are not necessarily subsets of each other allows us design anytime-learning approach. At any time, may stop the learning and compute a robust policy for the uMDP that the process has yielded thus far, together with the worst-case performance of this policy against a given specification. This performance may not be satisfactory, e.g., the worst-case probability to reach a set of critical states may be below a certain threshold. We continue learning towards new uMDP that more faithfully captures the true MDP due to the inclusion of further data. Thereby, we ensure that the robust policy gradually gets closer to the optimal policy for the true MDP.
Specification-driven. Our method features the possibility to learn in a task-aware fashion, that is, learn transitions that matter for a given specification. In particular, for reachability or expected reward (temporal logic) specifications which require certain set of target states to be reached, we only learn and update transitions along paths towards these states. Transitions outside those paths do not affect the satisfaction of the specification.
Adaptive to changing environment dynamics. When using linearly updating intervals, our approach is adaptive to changing environment dynamics. That is, if during the learning process the probability distributions of the underlying MDP change, our method can easily adapt and learns these new distributions.
2 Related Work
Uncertain MDPs have (often implicitly) been used by reinforcement learning (RL) algorithms, for instance, to optimize the exploratin/expllitttinn trade-off by guiding the RL agent towards unex- plored parts of the environment, following the optimism in the face of uncertaiuty principle [Jaksch] al. [2100] Fruit et al.) [0177]. We use the same principle in the exploration phase of our procedure, but compute robust policies as output to account for the uncertainty in an adversarial (or pessimistic) way. Similarly, uncertain MDPs are used to compute robust policies when the data available is limited NNilim and Ghaoui| 2005, Wiesemann et al. 2013 Russel and Petrik 2019]. Such robustness connected to a pessimistic principle that has been effective offline RI. settings (Lange et al.. 2012), where the agent only has access to fixed dataset of past trajectories, meaning it needs to base

---

decisions on limited data [Rashidinejad et al. [021] Buckman et al. 2021 Jin et al. 2021]. Likewise, our method may be stopped early and return a policy before the problem is fully explored.
Robust RI. concerns the standard RL problem, but explicitly accounts for input disturbances and model errors (Morimoto and Doya 2005]. Often there is focus on ensuring that reasonable performance is achieved during data collection. To that end. Lim et al. [2013] and Derman et al. (0199 sample trajectories using a robust policy, which can slow down the process to find an optimal policy. We assume sampling access to the underlying MDP, which allows us to use more efficient exploration. It should be noted that we only use uMDPs as an intermediate model towards learning a standard MDP, whereas in robust RL the model itself may also be an (adversarial) uncertain MDP. As a result, our method converges to an MDP, while robust RL attempts learn and possibly converge to an uncertain MDP.
Learning MDPs from data is also related to model learning, which typically assumes no knowledge about the states and thus iteratively increases the set of states [Vaandrager, 2017]. In [Tappler et al.) 2019, [022] the L algorithm for learning finite automata is adapted for MDPs. These methods only yield point estimates of probabilities, and make strong assumptions on the structure of the MDP that being leamned [Ahoo et al. [201]] use PAC-learnng to estimate the transition functions of MDPs and stochastic games in order to perform statistical model checking with a PAC guarantee on the resulting value. In [Bacci et al. 2021] the Baum- Welch algorithm for learning hidden Markov models
is adapted to learn MDPs.
Finally, the literature distinguishes two types of uncertainty: aleatoric and epistemic uncer- tainty [Hüllermeier and Waegeman, 202T]. Aleatoric uncertainty refers to the uncertainty generated by a probability distribution, like the transition function of an MDP, and is also known irreducible uncertainty. In contrast, epistemic uncertainty is reducible by collecting and accounting for (new) data. Our work can be seen as adding an additional layer of epistemic uncertainty on the probability distributions of the transition function that is then, by gathering and including more data, reduced.
3 Preliminaries
A discrete probability distribution over finite set X is function μ: X + [0, C R with Exex μ(x) = 1. We write D(X) for the set of all discrete probability distributions over X, and by |X| we denote the number of elements in X. For any closed interval I C R we write I and I for the lower and upper bounds of the interval, that is, I = [].
Definition 1 (Markov decision process). A Markov decision process (MDP) is a tuple (S, 81, A, P, R) with S a finite set of states, 81 E S the initial state, A a finite set of actions, P: S x A x S + [0, 1] with Vs, E S A, Σ.E. P(s, a, 8') function, and R: S x A- + Rzo the reward (or cost) function.
(such that P(s, a) (D(S)) the probabilistic transition
A trajectory in an MDP is finite sequence (Sp, an. $1 .i.......,,. E (S x A)* X S where sg Ss and P(ss, 0j 1) > O for 0 S < n. A memoryless policy is function x: S - -(().. If π maps to Dirac distributions, then it is a memoryless deterministic (or pure) policy. Applying policy to an MDP M resolves all the non-deteriinistic choices and yields an (induced) discrete-time Markov chain (DTMC); see, e.g., .ut.rrutemmmnn] (1994) for details.
Definition 2 (Uncertain MDP). An uncertain MDP (uMDP) tuple A,,,,, where S.81, A, R are as for MDPs, I is set of probability intervals I = {(a, b) 1 < a < < 1}, and P: x Ax S -> (TU (0)) is the uncertain transition function, assigning either a probability interval, or the exact probability 0 to any transition.
Uncertain MDPs can be seen as an uncountable set of MDPs that only differ in their transition functions. For a transition function P. we write P E P if for every transition the probability of P lies within the interval of P. i.c., ass,a,s') P(s, a, s") for all (s,a, E S x A x S. We only allow intervals with a lower bound greater than zero, to ensure a transition cannot vanish under certain distributions generated by the uncertainty. This assumption is standard in uMDPs (Wiesemann) et al. 2013 Puggelli et al.) 2013]. Applying a policy to a uMDP yields an induced interval Markoy chain [Jonsson and Larsen 1991].
Specifications. We consider reachability or expected reward (cost) specifications. The value P.M. (0 T') is the probability to reach set of target states T C S in the MDP M under the policy n,
3

---

also referred to as the performance of x Likewise, (0 describes the expected accumulated reward to reach T under æ. Note that for probabilisticc specifications, we can replace the formula T by more general reach-avoid specifications using the until operator from temporal logic.
Formally, the specification Max (6 T) max (O T) expresses that the probability of eventually reaching the target set I' C 5 should be maximized. Likewise, the specification (M T)) requires the expected reward for reaching T' be maximized. For minimization, we write Min ( T) and RMin() I',, respectively. Besides optimizing a probability or reward, a specification may also express an explicit user-provided threshold to compare the performance of policy to.
For uMDPs, we define optimistic and pessimistic specifications. In optimistic specifications, we assume the best-case scenario of the uncertainty to satisfy the specification by also minimizing (or maximizing) over the uncertainty set, written as FMinMin T) min, minpep PP (0 T) (or MaxxMax (0 T)), where the first Min (Max) signals what the decision-maker is trying to achieve, and the second what the uncertainty does. In pessimistic specifications, the uncertainty does the opposite of the goal: MaxMin (0 T') or MimMax (0 T). The notation is similar for reward specifications. A (standard) specification ip can be extended to be optimistic or pessimistic by adding a second Min or Max. We write yo for its optimistic extension, and yor for its pessimistic extension.
For an MDP M, the aim to compute a policy that either optimizes a given specification y or whose performance respects given threshold that, e-g., provides an upper bound on the probability of reaching a set critical states. Common methods are value iteration or linear programming [Puterman] 1994 Baier and Katoen 2008). For uncertain MDPs M, the goal is to compute policy that satisfies an optimistic or pessimistic specification yo or ypp. In the latter case, we call v a robust policy. Optimal policies in uMDPs can be computed via robust dynamic programming or convex optimization [Wolff et al. 2012 Puggelli et al. 2013).
4 Problem Statement and Outline of the Procedure
We have an unknown but fixed MDP M = (S, $1, A, A. R), which we will refer to as the true MDP, an initial prior uMDP M = (S, 87, I, R),, and specification yp which we
want to satisfy. A discussion of prior (and other parameter) choices follows in Section b
Assumption 1 (Underlying graph). We assume that the underlying graph of the true MDP is known. In particular: transitions that do not
Tuput
Anytime-learning procedure
Output
IMDP a4
Specifiztion
Robest Polley Computation
Notta policy
Leared M
kmP of
exist in the true MDP (transitions of probability 0) do also not exist in the uMDP, transitions of probability 1 in the true MDP are assigned the point interval [1, 1] in the uMDP, and any other transition of non-zero probability has an interval I E in the uMDP
Sample from ir
Update
Figure 1: Procedure outline.
Under Assumption and Definition 2 we construct the initial prior uMDP A to have transitions of probability 0 and 1 exactly where the true MDP M has these too, and interval transitions [s, s] for all other transitions, with ε > 0 free to choose. In particular, our approach does not require & to be smaller than the smallest probability p 0 occurring in M, which we also do not assume to be known. Alternatively, in case further knowledge available, one may use any other prior uMDP as long as it satisfies Assumption I
Our learning problem is expressed as follows:
The problem is to learn the transition probabilities of true MDP M, driven by specification y via intermediate uncertain MDPs M that are iteratively updated to account for newly collected data, such that at any time a robust policy can be computed.
In the following we outline our mnytime-learning procedure as illustrated in Figure I
1. Input. We start with an initial prior uMDP M and a specification & we wish to verify. We assume (black box) access to the unknown rrue MDP M to sample trajectories from, or alternatively, assume (constant) stream of observations from the true MDP
We will omit the policy and the MDP M whenever they clear from the context.

---

6-1-6
(...
Rizh R.zh.
k.1-1]
(a) The true MDP. (b) Assumption
1
(c) Initial prior.
(d) Intermediate uMDP
(c) Converging to- wards the true MDP.
Figure Process flow on an example MDP.
2. Robust policy computation. We compute robust policy for the pessimistic extension ip, i.c ipp, in the uncertain MDP M, together with the worst-case performance of the specification in the current uMDP. If the specification contains explicit threshold, the value can be compared against the threshold for automatic termination. In case of specifications that optimize probability reward, termination needs be done manually, as is impossible to tell if the maximum (minimum) was achieved.
3. Anytime learning. If the result from step is unsatisfactory, we start learning:
(a) Exploration. We sample one or more trajectories from the true MDP M, using the optimism in the face of uncertainty principle.
(b) Update. We update the intervals of the uMDP M in accordance with the newly collected data. This update yields a new uMDP that more faithfully captures all collected data up to this point than the previous uMDP.
(c) Repeat. We start again at step 2 with this new uMDP until (manual) termination.
4. Output. The process may be stopped at any moment and yields the latest uMDP M together with robust policy æ and the performance
on M.
The effects of this procedure are illustrated in Figure 2 In 2a and 2b shows the assumed knowledge about M. 2c shows the initial uMDP M constructed from 2b using (symbolic or explicit) lower bound greater than zero. In 2d we see an intermediate learned uMDP. Some intervals may already have successfully converged towards the probability of that transition in the true MDP, while others may be very inaccurate due to low sample size and thus a bad estimate. Finally, 2e depicts the learned uMDP converging towards the true MDP.
we an example MDP M to learn,
ensure that all lower bounds of M strietly
5 Bayesian Learning
We assume access to trajectories through the true MDP. Due to the Markov property of the MDP, i.c., the fact that the transition probabilities only depend on the current state and not on any further history, we may split each trajectory into separate sets of independent experiments where a state-action pair (s. is sampled and a successor state s; observed; see also Appendix of [Strehl and Littman 2008). We count the number of occurrences of the transition (s, 8;) in each trajectory and the number of occurrences of the state-action pair (s, a) in each trajectory т, denoted by #(s, a, s;) and #(s, a), respectively. In the following, we introduce the two approaches of learning intervals: the standard approach PAC learning via Hoeffding's 's inequality which provides PAC guarantee on the value of the learned model, and new approach using linearly updating intervals (LUI), which more flexible due to the inclusion of prior-data conflicts and its closure properties. Finally, we introduce minor modification to the LUI approach, making it also applicable to situations where the underlying MDP changes over time. Such a modification is not possible in PAC learning as Hoeffding's s inequality assumee independent samples from fixed distribution.
5.1 Learning PAC Intervals
We use the standard method of maximum a-posteriori probability (MAP) estimation to infer point estimates of probabilities; see Appendix A for details. These point estimates can then easily be turned into probably approximately correct (PAC) intervals via Hoeffding's 's inequality. Given N #(s, a) samples and a fixed error rate 7, we use Hoeffding's inequality (Hoefiding. 1963) to compute the
5

---

interval size 8 = /lo((/-)/2N. This å may then be used to construct intervals that are PAC with respect to the true transition probability, To lift the PAC guarantee the entire learned MDP. and consequently also the optimal value for some specification, we need to distribute á over all transitions, i.e., 6p = (ijex. (Suce(s.a)l, where Succ(s, a) is the set of successor states of (s, a). Using this 8p, we then construct the intervals
P(s, a, 8a) - [m P(s, a, 8:) - 6p), min (Pin, 8.) + 8p, 1)1,
where P the (MAP) point estimate, and is again a small value to ensure that the interval lower bounds are non-zero. As a result, we have the following Proposition, whose proof is a direct application of Hoeffding's inequality.
Proposition 1. The true MDP M lies within the learned uMDP M with probability greater or equal to --7-
This is standard result and also used in, e.g., PAC statistical model checking
[Ashok al. 2019
5.2 Learning Linearly Updating Probability Intervals
We use the Bayesian approach of intervals with linearly updating conjugate priors [Walter and Augustin 2009 learn intervals of probabilities. Each uncertain transition Ps,,a, a, 8;) is assigned prior interval P. [2.; Pt), and a prior strength interval [m,: n4.] that represents minimum and maximum number of samples on which the prior interval is based. The greater the values of the strength interval, the more emphasis placed on the prior, and the more data is needed to significantly change the prior when computing the posterior. The greater the difference between the n, and ni the greater the difference between a prior-data conflict and a prior-data agreement.
Definition 3 (Posterior interval computation). The interval [P;, Pi] can be updated to [Pl, PPl.P%), using N #(s a) and h; = #(s, a, si), as follows:
R2 m.P
if 2 P (prior-data agreement),
B N
(2)
B,P. P, +kz
jj vo
P, (prior-data conflict).
22 +
T., P.
if k
P3 (prior-data agreement),
P
(3)
R. P
if kg N P, (prior-data conflict).
2
The strength interval is updated by adding the number of samples N to it: [n W.] = + N,
The initial values for the priors of each state-action pair can be chosen freely subject to the constraints 0 < 2, < P. < 1, and n. 2 m4 2 1.
Key properties of linearly updating probability intervals.
Convergence in the infinite run. Under the assumption that the true MDP does not change, each interval will converge to the exact transition probability when the total number of samples processed tends to infinity, regardless of how many samples are processed per iteration [Watter and Augustin| 2009). This assumption is, however, not required for our work. If the true MDP changes over time, or is adversarial (i.e., uMDP). method is still applicable, but will not converge to a fixed MDP.
Prior-data conflict. When the estimated probability k//N lies outside the current interval, a so-called prior data conflict occurs. Consequently, if at some point we derive an interval that does not contain the true transition probability, the method will correct itself later on.
Closure properties under updating. Finally, updating is closed in two specific ways. First, any interval of probabilities is updated again to valid interval of probabilities, and second, any set of intervals at a state-action pair that contains a valid distribution over the successor states will again contain distribution over successor states after updating.
key requirement for computing robust policies on uMDPs is that the lower bound of every interval is strictly greater than zero (see Definition 2). This closure property is formalized as follows.

---

Theorem (Closure of intervals under learning), For any valid prior interval [P, P| with 0 < P S P S we have that the posterior [ P'] computed via Definition 3 also satisfies 0 < P' - P
Furthermore, we also have closure properties at each state-action pair. particular, we choose our prior intervals such that there is at least one valid probability distribution at the state-action pair, then the posterior intervals will again contain a valid probability distribution. We formalize this notion by examining the sum of the lower and upper bounds of the intervals in the following Theorem:
Theorem (Closure of distributions under learning). We have the following bounds on the set of posterior distributions. In case of a prior data agreement, we have that the sum of the posterior bounds is bounded by the sum of the prior bounds, and the value 1. That is,
EP.SIPISL
1 15 <<PP'>>>
(4)
In case of prior-data conflict, the sum of posterior bounds is no longer necessarily bounded by the prior, and we only have
EESIS DF.
(5)
Note, however, that this last constraint distribution at the state-action pair.
5 is already sufficient to ensure that there is a valid probability
The proof' for both Theorem Tand 2 can be found Appendix B.
5.3 Efficient exploration
Above, we assumed that a set of trajectories was given. To actually obtain the trajectories, we use the well-established optimism in the face of uncertainty principle [Munos] 2014). We compute the optimal policy for the optimistic extension (see Section (3 of the specification ye, i.e. 9o. in the current uMDP and use this policy for exploration. To make exploration specification-driven, we only sample transitions along trajectories towards the target state(s) of the specification. When the last seen state has probability zero one to reach the target for reachability, or reward zero or infinity, restart. States satisfying these conditions can be found by analyzing the graph of the true MDP [Baier and Katoen 2008
Trajectories and iterations. As explained in Section 4 our method iterative in terms of updating the uMDP M and computing robust policy. After updating the uMDP, we also compute new exploration policy, based on the new uMDP. Each iteration consists of processing at least one, but possibly more trajectories. To determine how many trajectories to collect, scheme, where we keep track of how often every state-action pair and transition is visited during exploration (Jin et al. 2020]. An iteration is completed when any of the counters is doubled with respect to the previous iteration. A detailed description of this schedule is given in Appendix C.
doubling-countee
5.4 Learning under changing environments
Previously, we assumed a fixed unknown true MDP A to learn. But what if the transition probabili- ties of M suddenly change? More precisely, we assume two unknown true MDPs, Mi and Mr with the same underlying graph but (possibly) different transition probabilities. After an unknown number of interactions with the true environment Mt, we suddenly continue interacting with Mý. We modify our LUI approach by introducing bound on the strength of the prior, 1M update the strength intervals by the following rule
Max Max) and
It'. [
[min(2, + N, min(;; + N, MMxx]]
The probability intervals themselves are updated in the same way as before in Definition 3 By limiting the prior strength in this way, trade some rate of convergence for adaptability. The weaker the prior, the greater the effect of a prior-data conflict, and hence adaptability to new data. When suddenly changing environments, new data will likely lead to prior-data conflicts, and thus higher adaptability of the overall learning method.
We add randomization to the pure optimistic exploration policy. We introduce hyperparameter E E [0, 1). and follow with probability & the action of the optimistic policy, and distribute the remaining 1 uniformly over the other actions, yielding memoryless randomized policy.
7

---

6 Experimental Evaluation
We implement our approach, with both linearly updating intervals (LUI) and PAC intervals (PAC), in Java on top of the verification tool PRISM (Kwiatkowska et al. 2011]. together with variant of value iteration to compute robust policies for uMDPs with convex uncertainties (Wolff et al. 2012 We compare our method to point estimates derived via MAP-estimation (MAP) and with uMDPs learned by the UCRL2 reinforcement learning algorithm Daksch et al., 2010] (UCRL2). We modify UCRL2 to make it more comparable to setting. In particular, we use optimistic policies for exploration, but robust policies to compute the performance, in contrast to the standard UCRL2 setting which only uses optimistic policies, see Appendix E for further details.
Without knowledge about the true MDP apart from Assumption [] we have to define an appropriate prior interval for every transition. We set ε = 1e-4 as constant and define the prior uMDP with intervals P; |e, 1 - E] and strength intervals [m,, 7i. = [5, 10] at every transition ((s, a, 8,), as in Figure 2c For MAP, we use prior of a; = 10 for all i. The same prior is used for the point estimates both PAC and UCRL2, together with an error rate of y = 0.01.
Evaluation metrics.
We consider two metrics evaluate the four learning methods.
Performance. How does the robust policy computed on the learned model perform on the true MDP? We evaluate the probability of satisfying the given specification PM (9 T) or expected reward R (o T) of the robust policy π computed after each update of the model.
Performance estimation error: How well do we expect robust policy perform on the true MDP based on the performance on the intermediate learned uMDP? We compute the difference between the performance of the robust policy on the learned uMDP (the worst-case performance) and the performance on the true MDP. While values closer to zero are preferable, we do not accept methods with positive estimation errors, since this indicates their estimated performance is not lower (conservative) bound the actual performance the policy. In particular, an estimation error above zero shows the policy is misleading in terms of predicting its performance.
We benchmark our method using several well known environments: the Chain Problem Araya-Lóppz et al. 2011), Aircraft Collision Avoidance [Kochenderfer] (0015) slippery Grid World [Derman 2019 a 99-armed Bandit [Lattimore and Szepesvári] (020), and two version of a Betting et al.
Game Bäuerle and Ott/ 2011]. For details on all these environments we refer to Appendix D. We highlight the Betting Game and Chain Problem environments here, as they will be used to explain some of the key observations we make from our experimental results.
Betting Game. The agent starts with 10 coins and attempts to maximize the number of coins after 6 bets. When a bet is won, the number of coins placed is doubled; when lost, the number of coins placed is removed. The agent may bet 0, 1, 2, 5, or 10 coins. We consider two versions of the game, one which is favourable to the player, with a win probability of 0.8, and one that is unfavourable with win probability 0.2. After 6 bets the player receives reward equal to the number coins left. The specification is to maximize the reward.
Chain Problem. We consider a chain of 30 states. There are three actions, one progresses with probability 0.95 to the next state, and resets the model to the initial state with probability 0.05. The second action does the same, but with reversed probabilities. The third action has probability 0.5 for both cases. Every action gets reward of 1. As specification, minimize the reward to reach the last state of the chain.
Results
We present an excerpt of our experimental results here, and refer the reader to Appendix F for the full set of results, which in particular also includes the estimation error for all environments, model error metric, and further experiments regarding different priors and changing environments. All experiments were performed on a machine with a 4GHz Intel Core 19 CPU, using single core. Each experiment is repeated 100 times, and reported with a 95% confidence interval.
additional
'The implementation is available

---

LUI
MAP
UCRL
PAC
Bentig Townardhe
Bentnn Utisseanhle
Alczah
1.3
32103)
22103)
2200
1.30
0.32
Trpeowey
Bands
Clain Large
Gii
033
-2000
30
21:01
P2105)
0.01
12
100
Tegorery
Tejeiry
Figure 3: Comparison of the performance of robust policies different environments against the number trajectories processed (on log-scale). The dashed line indicates the optimal performance.
Beting
Beting
bemambbrr
300
300
120
16
Figure 4: Estimation eπrо on the two Betting Game environments and the Bandit, against the number of trajectories processed (on log-scale).
shows the performance of the robust policies computed via each learning method against the number of trajectories processed on the different environments. We first note that in all environments, our LUT method the first to find an optimal policy. Depending on the environment, the performance of L.UI and PAC may be roughly equivalent (Chain, Grid), When also taking the estimation enror into account (Figure 4 we see I.UI outperforming other methods on that metric. UCRL2 is the slowest to converge an optimal policy. This due UCRL2 being reinforcement learning algorithm, and thus is slower in reducing the intervals favour of a broader exploration.
Recovering from bad estimates. On the Chain environment, we see LUI and PAC (around trajectory 5), and UCRL2 (around trajectory 10") choose the wrong action(s), with an decrease in performance as a result. This is most likely due to getting bad estimate on some of the transitions later on in the chain, leading to many resets to the initial state, and thus decreasing the performance significantly. While all three methods manage recover and then find the optimal policy, UCRL2 takes significantly longer: only after trajectory 10S, where LUI and PAC only need about 100 trajectories. -at-emtimation typically sits between LUI and PAC terms of performance. It less sensitive to mistakes like the one discussed above, but is less reliable in providing conservative bound on its performance, as will be discussed below. Furthermore, we see that in the unfavourable Betting Game, only MAP-estimation gives sub-optimal performance, due to bad estimates. It is able to recover from this, but needs almost 10a trajectories to do so. Due to the low win probability in this Betting Game, robust policy the uMDPs is by default optimal policy for the true MDP, and we see that LUI, PAC, and UCRL2 do not change to a sub-optimal policy.
Robust policies are conservative. Consider Figure 4 We note the undesirable behaviour of having an Estimation Error above zero, which means the performance of the policy the learned model

---

"Maa (20, 30)
"Mux
"Max (20,
"Max [20,
1000000
75000
(0
50000
25000
200, 3001
100
"Max 1200, 300]
1000
1200, 300)
1- 10000
[200, 300] -T- 100000
100000
Algoiilm
(O
50000
LUI
MAP
25000
UCRI
"Max 100.00) 00)
"Max
1000
MMa [20, ool
f- 10000
"Max -
102000
75000
(O
50000
107
10
10²
10f
Trajectory
Trijctory
Trijector
Trajectory
Figure 5: Environment change on the Chain Problem at different points f E {10?,... 10ah using randomization parameter & 0.8 in the exploration.
was higher than the performance of that policy on the true MDP. MAP-estimation is particularly susceptible this, while all three uMDP methods yield policies that are conservative in general. though some exceptions exist as shown in the full results in Appendix F.
LUI is adaptive changing environments. Finally, investigate the behaviour of the learning methods when after fixed number of trajectories the probabilities of the true MDP change, as introduced in Section 5.4 Figure 5 shows the performance of the robust policy for each learning method on the Chain environment, results for the same experiment on the Betting Game can be found in Appendix F.After E {102, transition probabilities, for three different bounds on the strength intervals. We similarly bound the MAP-estimation priors for MAP and UCRL. PAC omitted from this experiment as PAC guarantees lose all meaning when changing the underlying distribution. After the change in environment, the new optimal policy has to use the opposite action from the previously optimal policy. We see that LUI is the only method capable of converging optimal policies both before and after the change in environment. Furthermore, the lower the bounds on the prior strength, the faster it adapts to the change. We conclude that LUI is effective approach to deal with learning an MDP under potential adversarial sampling conditions.
10") trajectories, we change the environment by swapping the
Conclusion and Future Work
We presented a new Bayesian method that learns uMDPs to approximate MDP, either via linearly updating intervals, or PAC-intervals. Robust policies computed on learned uMDPs are shown to be conservative and reliable in predicting their performance when applied the MDP that is being learned. The approach of linearly updating intervals is also effective at continuously learning potentially changing environment. For future work, we aim to extend our method uncertain POMDPs (Suilen et al. 2020, (Cbbuttppe et al. [02T]] While we do not see any immediate negative societal impacts of our work, we acknowledge that potential misuse of our work cannot be ruled out due to the generality of MDPs.
10

---

References
Mauricio Araya-LLópez, Olivier Buffet, Vincent Thomas, and François Charpillet. Active Learning of MDP Models. In EWRL, volume 7188 of LNCS, pages 42-53. Springer, 2011.
Pranav Ashok, Jan Kretínský, and Maximilian Weininger. PAC Statistical Model Checking for Markov Decision Processes and Stochastic Games. CAV (1), volume 11561 of LNCS, pages 497-519. Springer, 2019.
Giovanni Bacci, Anna Ingólfsdóttir, Kim G. Larsen, and Raphaël Reynouard. Active Learning of Markov Decision Processes using Baum- Seln- algorithm. In ICMLA, pages 1203-1208. IEEE, 2021.
Christel Baier and Joost-Pieter Katoen. Principles of model checking. MIT Press, 2008.
Nicole Bäuerle and Jonathan Ott. Markov Decision Processes with Average-Value-at-Re criteria. Math. Methods Oper. Res., 743):361-379, 2011.
Dimitri P. Bertsekas. Dynamic programming and optimal control, 3rd Edition. Athena Scientific, 2005.
Jacob Buckman, Carles Gelada, and Mare G Bellemare. The Importance of Pessimism in Fixed- Dataset Policy Optimization. In /CLR, pages 1-11. OpenReview.net, 2021.
Murat Cubuktepe, Nils Jansen, Sebastian Junges, Ahmadreza Marandi, Marnix Suilen, and Ufuk Topcu. Robust Finite-State State Controllers for Uncertain POMDPs. In AAAI, pages 11792-11800.
AAAI Press, 2021.
Esther Derman, Daniel J. Mankowitz, Timothy A. Mann, and Shie Mannor. A Bayesian Approach to Robust Reinforcement Learning. UAI, volume 115 of Proceedings of Machine Learning Research, pages 648 658. AUAI Press, 2019.
Ronan Fruit, Matteo Pirotta, Alessandro Lazaric, and Emma Brunskill. Regret Minimization in MDPs with Options without Prior Knowledge. In NIPS, pages 3166-3176, 2017.
Vineet Goyal and Julien Grand-Clement. Robust Markov Decision Process: Beyond Rectangularity, 2020.
Wassily Hoeffding. Probability Inequalities for Sums of Bounded Random Variables. Journal of the American Statistical Association, 58(301): 1963.
Eyke Hüllermeier and Willem Waegeman. Alcatoric and epistemic uncertainty in machine learning: an introduction to concepts and methods. Mach. Learn., 1 10(())4577-50) 2021.
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal Regret Bounds for Reinforcement Learning. J. Mach. Learn. Res., 11:1563-1600, 2010.
Chi Jin, Tiancheng Jin, Haipeng Luo, Suvrit Sra, and Tiancheng Yu. Learning Adversarial Markov Decision Processes with Bandit Feedback and Unknown Transition. In ICML, pages 4860-4869, PMLR, 2020.
Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is Pessimism Provably Efficient for Offline RL? In ICML, pages 5084-5096. PMLR, 2021.
Bengt Jonsson and Kim Guldstrand Larsen. Specification and refinement of probabilistic processes. In IJCS, pages 266-277. IEEE Computer Society, 1991.
Mykel Kochenderfer. Decision making under uncertainty: theory and application. MIT press, 2015.
Marta Z. Kwiatkowska, Gethin Norman, and David Parker. PRISM 4.0: Verification of Probabilistic Real-Time Systems. In CAV, volume 6806 of LNCS, pages 585-591. Springer, 2011.
Sascha Lange, Thomas Gabel, and Martin Riedmiller. Batch Reinforcement Learning. In Marco A
Wiering and Martijn van Otterlo, editors, Reinforcement Learning: State-of-the-Arl, pages 45-73. Springer Berlin Heidelberg, Berlin, Germany, 2012.

---

Tor Lattimore and Csaba Szepesvári. Bandit Algorithus. Cambridge University Press, 2020.
Shiau Hong Lim, Huan Xu, and Shie Mannor. Reinforcement Learning in Robust Markov Decision Processes. In NIPS, pages 701-709, 2013.
Shie Mannor, Duncan Simester, Peng Sun, and John N. Tsitsiklis. Bias and Variance Approximation in Value Function Estimates. Manag, Sci., 53(2):308-333 2007.
Thomas M. Moerland, Joost Broekens, and Catholijn M. Jonker. Model-based Reinforcement Learning: A Survey. CoRR, abs/2006.16712 2020.
Jun Morimoto and Kenji Doya. Robust reinforcement learning. Neurul Comput., 17(2):335-359, 2005.
Rémi Munos. From Bandits to Monte-Carlo Tree Search: The Optimistic Principle Applied to Optimization and Planning. Found. Trends Mach. Learn., 7(1):1-129, 2014.
Arnab Nilim and Laurent El Ghaoui. Robust Control of Markov Decision Processes with Uncertain Transition Matrices. Oper. Res., 53(5)7880-798, 2005.
Amir Pnueli. The Temporal Logic of Programs, In FOCS, pages 46-57. IEEE Computer Society, 1977. doi: 10. 109/SFC/.. 1977.32.
Alberto Puggelli, Wenchao Li, Alberto L. Sangiovanni- Sangiovanmi-Vincntelli, and Sanjit A. Seshia. Polynomial- Time Verification of PCTL Properties of MDPs with Convex Uncertainties. In CAV, volume 8044 of LNCS, pages 527-542. Springer, 2013.
Martin L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley
Series in Probability and Statistics. Wiley, 1994.
Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart Russell. Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism. In NeurIPS. Curran Associates, Inc., 2021.
Mare Rigter, Bruno Lacerda, and Nick Hawes. Minimax Regret Optimisation for Robust Planning in Uncertain Markov Decision Processes. In AAAI, pages 11930-11938 AAAI Press, 2021.
Reazul Hasan Russel and Marek Petrik. Beyond Confidence Regions: Tight Bayesian Ambiguity Sets for Robust MDPs. In NeurlPS, pages 7047-7056, 2019.
Alexander I.. Strehl and Michael L.. Littman. An analysis of model-based Interval Estimation for Markov Decision Processes. J. Comput. Syst. Sei., 1409):130-11331 2008
Alexander L. Strehl, Lihong Li, and Michael L. Littman. Reinforcement Learning in Finite MDPs: PAC Analysis. J. Mach. Learn. Res., 10:2413-2444, 2009.
Marnix Suilen, Nils Jansen, Murat Cubuktepe, and Ufuk Topcu. Robust Policy Synthesis for Uncertain POMDPs via Convex Optimization. In IJCAI, pages 4113-4120. ijeai.org, 2020.
Martin Tappler, Bernhard K. Aichernig, Giovanni Bacci, Maria Eichlseder, and Kim G. Larsen. L* Based Learning of Markov Decision Processes. In FM, volume 11800 of LNCS, pages 651-669. Springer, 2019.
Martin Tappler, Edi Muskardin, Bernhard K. Aichernig, and Ingo Pill. Active model learning of stochastic reactive systems. In SEFM, volume 13085 of Lecture Notes in Computer Science, pages 481-500. Springer, 2021.
Frits W. Vaandrager. Model learning. Commun. ACM, 60(2):86 9518886695,,00 2017.
Gero Walter and Thomas Augustin. Imprecision and prior-data conflict in generalized Bayesian inference. Journal of Statistical Theory and Practice, 3(1):255-271, 2009.
Wolfram Wiesemann, Daniel Kuhn, and Berç Rustem. Robust Markov Decision Processes. Math. Oper: Res., 38(1): 2013.
Eric Wolff, Ufuk Topeu, and Richard M. Murray. Robust control of uncertain Markov Decision Processes with temporal logic specifications. In CDC, pages 3372-3379, IEEE, 2012.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes] We briefly
reflect on this in the conclusion.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to
them? [Yes] All experiments were on standard desktop PC, see Section 6
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Assump- tion particular.
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix B in particular.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material or URL)? [Yes] See supple- mentary material for the code and instructions on how to reproduce the results in the paper.
(b) Did you specify all the training details (c.g., data splits, hyperparameters, how they were chosen)? [Yes] All priors and other parameters are mentioned where relevant.
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes] All experiments are repeated 100 times and reported with 95% confidence intervals, as also mentioned in Section 6
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Section 6
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes] See Appendix for descriptions.
(b) Did you mention the license of the assets? [Yes] License is included in the supplemen- tary material (GNU general public license).
(c) Did you include any new assets either in the supplemental material or as URL? [Yes] See the models folder in the supplementary material. In particular, translated the existing models from the literature into the Prism language.
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "xAPrLM8cej3", "reviewer": "Reviewer_r6yL", "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. ", "questions": "1. Are there any insights/examples that illustrate when the approach leads to optimal policies? And poor policies?\n\n2. When would LUI be preferable to PAC? While this was discussed briefly, I feel that some clarifications could be extremely helpful. ", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- Innovative robust perspective to learn transition probabilities\n- Excellent exposition\n\nWeaknesses\n- Lack of theoretical insights\n- Limited numerical analysis\n\nMajor Comments\n\nOverall, 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:\n\n(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? \n\nPerhaps 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. \n\n(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.\n\nMinor Note\n- Proof *of* Proposition 1\n\n\n\n\n\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "QEeK-yRSwT", "reviewer": "Reviewer_2Job", "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).", "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?\n\nPage 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.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nThe 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "LekFmgkp-nS", "reviewer": "Reviewer_CuSo", "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.", "questions": "1. How is the PAC result employed given the distribution shift? Is this update procedure not iterative?\n1. 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?\n1. 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.\n- Not as fast as robust RL baseline at adapting to distribution shift. This is understandable and listed as future work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n1. The problem is well motivated and of interest to this venue.\n1. The approach builds off of well established theoretical machinery and combines them in a well motivated way.\n1. The baselines and metrics seem reasonable and help illustrate the strength of the approach.\n\n# Weaknesses\n1. (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.\n1. Need to know a-priori which transitions are impossible. This seems reasonable in many domains, but limits the applicability.\n1. Unclear how this approach scales to very large state and action spaces. \n1. Arguably an incremental result that builds on well established machinery.\n1. (minor) Does not easily detect that there has been a distribution shift (change of environment). This is left as future work.\n1. **(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.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept