Efficient Inference and Exploration for Reinforcement Learning
Authors: Yi Zhu
Jing Dong
Henry Lam
Venue:  (2020)
Keywords: Reinforcement Learning
Efficient Exploration
Asymptotic Analysis
Statistical Inference

Abstract: Despite an ever growing literature on reinforcement learning algorithms and applications, much less is known about their statistical inference. In this paper, we investigate the large-sample behaviors of the Q-value estimates with closed-form characterizations of the asymptotic variances. This allows us to efficiently construct confidence regions for Q-value and optimal value functions, and to develop policies to minimize their estimation errors. This also leads to a policy exploration strategy that relies on estimating the relative discrepancies among the Q estimates. Numerical experiments show superior performances of our exploration strategy than other benchmark approaches.

Under review conference paper at ICLR 2020
EFFICIENT INFERENCE AND EXPLORATION FOR REIN- FORCEMENT LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Despite an ever growing literature on reinforcement learning algorithms and ap- plications, much less is known about their statistical inference. In this paper, we investigate the large-sample behaviors of the Q-value estimates with closed-for form characterizations of the asymptotic variances. This allows us to efficiently construct confidence regions for Q-value and optimal value functions, and to develop policies to minimize their estimation crrors. This also leads to policy exploration strategy that relies on estimating the relative discrepancies among the Q estimates. Numeri- cal experiments show superior performances of our exploration strategy than other benchmark approaches.
1 INTRODUCTION
We consider the classical reinforcement learning (RL) problem where the agent interacts with a random environment and aims to maximize the accumulated discounted reward over time. The environment formulated as a Markov decision process (MDP) and the agent is uncertain about the true dynamics to start with. As the agent interacts with the environment, data about the system dynamics are collected and the agent becomes increasingly confident about her decision. With finite data, however, the potential reward from each decision is estimated with errors and the agent may be led to a suboptimal decision. Our focus this paper is on statistically efficient methodologies to quantify these errors and uncertainties, and to demonstrate their use in obtaining better policies.
More preciscly, we investigate the large-sample behaviors of estimated Q-value, optimal value function, and their associated policies. Our results are in the form of asymptotic convergence to an explicitly identified and computable Gaussian (or other) distribution, as the collected data sizes increase. The motivation of our investigation is three-fold. First, these precise asymptolic statements allow us to construct accurate confidence regions for quantities related to the optimal policy, and, like classical statistical inference, they can assess the reliability of the current estimates with respect to the data noises. Second, our results complement some finite-sample error bounds developed in the literature (Kearns & Singh, 1998 Kakade 20033 Munos & Szepesvári (2008), by supplementing a closcd-form asymptotic variance that often shows up in the first-order terms in these bounds.
Our third and most important motivation is to design good exploration policies by directly using our light error estimates. Motivaled by recent aulonomous-drivvng and other applications (e.g., Kalashnikov et al. (2018)), ), we consider the pure exploration selting where an agent first assigned an initial period to collect as much experience trained offline, starts deployment to gain reward. We propose an efficient strategy to explore by optimizing the worst-case estimated relative discrepancy among the Q-values (ratio of mean squared difference to variance), which provides a proxy for the probability of selecting the best policy. Similar criteria have appeared in the so-called optimal computing budget allocation (OCBA)
possible, and then, with the optimal policy

---

Under review conference paper at ICLR 2020
procedure in simulation-based optimization (Cen & Lee 2011 (a problem closely related to best-arm identification (Audibert & Bubeck 2010) in online learning). In this approach, one divides computation (or obscrvation) budget into stages in which one soquentially updates mcan and variance estimates, and optimizes next-stage budget allocations according to the worst-case relative discrepancy criterion. Our proposed procedure, which we term Q-OCBA, follows this idea with a crucial use of our Q-value estimates and randomized policies to achieve the optimal allocation. We demonstrate how this idea consistently outperforms other benchmark exploration policies, both in terms of the probability in selecting the best policy and generating the tightest confidence bounds for value estimates at the end of the exploration period.
Regarding the problem of constructing tight error estimates in RL, the closest work to ours is Mannor et al. (2004] 2007], which studics the bias and variance in value function estimates with a fixed policy. Our technique resolves main technical challenge in Mannor et. al.
(2004 2007], which allows us to
substantially generalize their variance results to Q-values, oplimal value lunctions and asymplotic
distributional statements. The derivation in Mannor et al. (2004 2007) hinges on an expansion of the value function in terms of the perturbation of the transition matrix, which (as pointed out by the authors) is not easily extendable from a fixed-policy to the optimal value function. In contrast, our results utilize an implicit function theorem applied to the Bellman equation that can be verified to be sufficiently smooth. This idca turns out to allow us to obtain gradients for Q-values, translate to the optimal value function, and furthermore generalize to similar results for constrained MDP and approximate value iterations. We also relate our work to the line of studies on dynamic treatment regimes (DTR) (Laber et al., 2014) applied commonly in medical decision-making, which focuses on results
the statistical properties of polices on finite horizon (such as two-period). Our infinite-horize on the optimal value and Q-value distinguishes our developments from the DTR literature. Moreover, our result on the non-umique policy case can be demonstrated to correspond to the "non-regularity" concept in DTR, where the true parameters are very close to the decision "boundaries" that switch the optimal policy (motivated by situations of small treatment effects), thus making the obtained policy highly sensitive to estimation noises.
In the rest of this paper, we first describe our MDP selup and notations (Section 2 Then we present our results on large-sample behaviors (Section 3 demonstrate their use in exploration strategies (Section 4 and finally substantiate our findings with experimental results (Section 5 In the Appendix, we first present generalizations of our theoretical results to constrained MDP and problems using approximate value iteration (..2.. Then we include more numerical experiments Bi, followed by all the proofs (C.
A.
2 PROBLEM SETUP
Consider an infinite horizon discounted reward MDP, M (S, where S is the state space, A is the action space, R(s, a) denotes the random reward when the agent is in state s S and selects action a E A, P(s'|s, a) is the probability of transitioning to state s' in the next epoch given current state s and taken action a, y is the discount factor, and p is the initial state distribution. The distribution of the reward R and the transition probability P are unknown to the agent. We assumne both S and are finite sets. Without loss of generality, we denote S= (1, m2} and A= 21, M.). Finally, we make the following stochasticity assumption: Assumption 1. R(s,a) a) has finite mean p a) and fonite variance [ a) V S, E A. For any given& E S and E A, R(s.a) and S' ~ P(-|s, a) are all independent random variables.
A policy π is mapping from each state S to probability measure over actions A. Specifically, we write π (a]s) as the probability of taking action a when the agent is in state s and π (-|ss) as the m dincnsional vector of action probabilities at state s. For convenience, we sometimes write r(s) as the
2

---

Under review conference paper at ICLR 2020
realized action given the current state is s. The value function associated with policy defined as (s) = E R(s,, (s:))]ss- = s] with 8++1 ~ P(.[st, Ts))). The expected value function, under the initial distribution p. denoted by X = E. ((s)VT(ss) (s). policy T' said be optimal if v** (s) = max; (s) for all 8 E S. For convenience, we denote V = V=* and x = V(s)) The Q Q-value, denoted by ((s, a), is defined as Q(s, a) Mrrls, a) + a). Correspondingly, (s) = max, ((8,a) and the Bellman equation for Q takes the form
((. = pR(s, a) + y1 max Q a') ds)l
(1)
for any (s, E E x A. Denoting the Bellman operator P.), Q is fixed point associated with P, ie. Q = (QQ.
For the most part of this paper we make the following assumption about Q:
Assumption 2. For any state s E S, arg m Q(s, a) is unique.
Under Assumption 2 the optimal policy n² is unique and deterministic. Let a²(s) arg m as) Then =*(als)= - 1 (a = (s)), where I[:) denotes the indicator function.
We next introduce some statistical quantities arising from data. Suppose have ob- servations (whose collection mechanism will be made precise later), which we denote as {(s,, at, (5( s)
1 S t S n), where re(s;, is the realized reward at time t and (8,, az) = 8411- We define the sample mean fnnn and the sample variance 0h,, of the reward as
(n, = (i = Eisrsn relst, (s) i, =
(2)
Eisien 1(s: = i1 =)
is= = Eisisn relse, (,) i, 5)
-Ann(i,))
(3)
Eisesn 11: i, =)
Similarly, define the empirical transition matrix Pa
Pa(s' = k|s i =) Eistsn 1(s = i, a: = j, (8,, 0z) = k)
(4)
Eisign 18x, = i, az =
and its m, x m, sampling covariance matrix Dp,,,
(with one sample point of (st = 8, at = a))
Ep., (ki, k2) = (( P(kals,a)) a))
kn = for 1 S kn S m, 1 S k2 S ms
(() h1 + k2.
With the data, we construct our estimate of Q, called Qn, which is the empirical fixed point of T P.. Pr: i.e. Qn = P. (Qn). Correspondingly, we also write (*) = max (=,8,)) and Xt = E.es (())
We shall focus the empirical errors due to noises of the collected data, and assume the MDP Q-value evaluation can be done off-line so that the fixed point equation for Qn can be solved exactly.
3 QUANTIPYING ASYMPTOTIC ESTIMATION ERRORS
We present an array of results regarding the asymptotic behaviors of Q, and Vz- To prepare, we first make an assumption on our exploration policy to gather data. Define the extended transition probability pa P al|s,
We make the assumption:
3

---

Under review conference paper at ICLR 2020
Assumption 3. The Markov chain with transition probobility pr is positive recurrent.
Under Assumption 3 pd has unique stationary distribution, denoted w, equal to the long run frequency in visiting each state-action pair, i.c. w(s, a) = lim Eisegn [(s = i, 2=
= j). where all w(s a''s are positive. Note that Assumption 3 is satisfied if for any two states s,s,, there exists a sequence of actions such that s' is attainable from under P. and, moreover, if π is sufficiently mixed, e.g,, satisfies x <<alss') > 0 for all s',a'
Our results in the sequel uses the following further notations. We denote "=" as "convergence in distribution", and (i,, Σ) as multivariate Gaussian distribution with mcan vector and covariance matrix Σ. We write as the identity matrix, and 6; as the i-th unit vector. The dimension of Nu,, Σ), I and should be clear from the context. When not specified, all the vectors are column vectors. Let N = m. In our algebraic derivations, we need to re-arrange PR: Q and w as N-dimensional vectors. We thus define the following indexing rule: (s=i,e i, = j) is re-indexed as (i (i-1)nm 1)mm + J c-g. pn(i,j) pn((i- 1)m + +))- We also need to re-arrange Pa
N N matrix following the same indexing rule, i.e. px (il, ((( Pm ((i 1)ma, + J, (i' 1) j').
3.1 LIMIT THEOREMS UNDER SUFFICIENT EXPLORATION
We first establish the asymptotic normality of Qn under exploration policy x: Theorem 1. Under Assumplions 7 and if the data is collected according to ı satisfying Assumption
5 then Qn is strongly consistent estimator of Q, i.c. Qn 7 Q almost surely - co. Moreover,
Vn(Q2. Q) - E) as n - 0c;
where
Σ -I - - (DR D2)((T - - -p-
(5)
W, DR and Dq are N x N diagonal matrices with
W(i - 1)m, + j, (i 1)m, + 5) w(i.j), Dn((i 1)m, + + (i - 1)m, + (i.))
and Dol(i - 1)m, + j. (i 1) + +) = (V*)² V respectively
In addition to the asymptotic Gaussian behavior, a key element of Theorem is the explicit form of the asymptotic variance Σ. This is derived from the delta method (Serfling 2009) and, intuitively, is the product of the sonsitivitics (i.c., gradient) of Q with respect to its parameters and the variances of the parameter estimates. Here the parameters are μR and P, with corresponding gradients (I (I-PP=") and (I 11P=="--1pp The variances of these parameter estimates (i.e., 2 and (4) involve (i. and Ep..: and the sample size allocated to estimate each parameter, which proportional to j)
Using the relations that (s) max Q(s, a) and Vi)()) max.e Qn(s,a), we can leverage Theorem [ to further establish the asymptotic normality of Vi and X:: Corollary 1. Under A Assumptions
and
VilV V*) = NN Ev) and Vnlii - x))
as +
where
Ey = (I - 11--P""---- > ( + DV - 7pp"
2f = Evp, ps is an m, x m, transition matria with p. (i,j) = P(j|s a = (s)), W", DR and DV are m, m. diagonal matrices with W= (i, a(i,a" D (i, = ( and D (i,1) (V') pp. V respectively.
4

---

Under review conference paper at ICLR 2020
In the Appendix we also prove, using the same technique as above, a result on the large-sample behavior of the value function for fixed policy (Corollary 2). which essentially recovers Corollary 4.1 in Mannor et al. (2007). Different from Mannor et al. (2007), we derive our results by using an implicit function theorem on the corresponding Bellman equation to obtain the gradient of Q, viewing the latter as the solution to the equation and as a function of μR,, P. This approach is able to generalize the results for fixed policies in Mannor et al. (2007) to the optimal value functions, and also provide distributional statements as Theorem I and Corollary []] above. We also note that another potential route to obtain our results is to conduct perturbation analysis the linear program (L.) representation of the MDP, which would also give gradient information of V (and hence also Q), but using the implicit function theorem here seems sufficient.
Theorem and Corollary | can be used immediately for statistical inference. In particular, we can construct confidence regions for subsets of the Q-value jointly, or for linear combinations of the Q-values. A quanlity of interest that we will later utilize in designing good exploration policies is Q(s.aj) a1) - ((. 02), ie. the difference between action 0r and 0g when the agent in state s. Define TQ as
(2 02) = (e(s-1)ma+ar c(s-1)m,+oe ) ( t)m - (1s-1)m,aa)
(6)
and its estimator AQ.x by replacing Q, V*, R.n w, P with Qu, 0 th, Pa in E, where Wn is the empirical frequency of visiting each state-action pair, i.e. wn (i,j) " Eisrsa 1(; i, at = j). Then the 100(1 a)% confidence interval (CI) for Q(s,a1) Q(s, 02) takes the form (Qn(s,an) - a2)) + Zo a1,)), where Za the (1 - -uuanniua of (0)
3.2 NON-UNIQUE OPTIMAL POLICY
Suppose the optimal policy for the MDP M is not unique, i..., Assumption 2 does not hold. In this situation, the estimated Qn and Va may "jump" around different optimal actions, leading to more complicated large-sample behavior as described below:
Theorem 2. Suppose Assumptions and 3 hold but there is no unique optimal policy. Then there crists K distinct m, (Nm, + NN matrices [GR]iegk and a deterministic partition Of {u Nm,,+mm,, : :||u|| = =] = UiskS Us such that VV( V*) + Σk G&1 (2/11211 E U2) Z, where = (O, ER,P), ER, = (W- Dp) and Dp =
+ 1), 1), Epp,//(((i
1)m, +)...... P..i..mmmm hww..//w((nnr) /w[(m,- 1)ma +.
In the case that K > 1 in Theorem 2 the limit distribution becomes non non-Gaussian. This arises because the sensitivity to P or μn can be very different depending on the perturbation direction, which is a consequence of solution non-uniqueness that can be formalized as non-degeneracy in the LP representation of the MDP. We note that this phenomenon is analogous to the "non-regularity" concept in DTR that arises because the "true" parameters in these problems are very close to the decision "boundaries", which makes the obtained policy highly sensitive to estimation noises and incurs 1/Vn-order bias behavior. Our case of non-unique optimal policy here captures precisely this same behavior, where we see in Theorem that when K > the asymptotic limit no longer has mean zero and consequently 1/vn-orrdr bias arises.
We also develop two other generalizations of largo-sample results, for constrained MDP and approxi- mate value iteration respectivcly (sec Appendicos A.1 and A.2
5

---

Under review conference paper at ICLR 2020
4 EFFICIENT EXPLORATION POLICY
to design exploration policies. We focus on the setting where an agent is assigned period to collect data by rumning the state transition with an exploration policy. The goal is to obtain the best policy at the end of the period in a probabilistic sense, i.e., minimize the probability of selecting a suboptimal policy for the accumulated reward.
We utilize our results in Section 3
We propose a strategy that maximizes the worst-case relative discrepancy among all Q-value estimates. More preciscly, we define, for E E and j + a (i), the relative discrepancy as has = (Q(ii (i.,))) /02 (i),)).
where iq(i, (1), is defined in 16) Our procedure attempts to maximize the minimum of hiy 's,
max min min hij.
(7)
NEW, iES jEA.)
where w denotes the proportions of visits on the state-action pairs, within some allocation set W, (which we will explain). Intuitively, hay captures the relative "difficulty" in obtaining the optimal policy given the estimation errors of Q's. Tf the Q-values are far apart, or if the estimation variance small, then hy is large which signifies an "casy" problem, and vice versa. Criterion (7) thus aims to make the problem the "casiest". Alternatively, one can also interpret 77 from a large deviations view Gllyn & Juneja 2004 Dong & Zhu 2016). Suppose the Q-values for state between two different actions a" (t) and J are very close. Then, one can show that the probability of suboptimal selection between the two has roughly exponential decay rate controlled by haj. Obviously, there can be many more comparisons to consider, but the exponential form dictates that the smallest decay rate dominates the caleulation, thus leading to the inner min's 's in 77. Criterion like 77) is motivated from the OCBA procedure in simulation optimization (which historically has considered simple mean-value alternatives (Chen & Lee 2011)). Here, we consider the Q-values. For convenience, we call our procedure Q-OCBA.
Implementing criterion ( requires two additional considerations. First, solving 7 needs the model primitives Q, P and o that appear in the expression of hty- These quantities are unknown a priori, but as we collect data they can be sequentially estimated. This leads to a multi-stage optimization plus parameter update scheme. Second, since data are collected through running a Markov chain on the exploration actions, not all allocation w admissible, i.e., realizable as the slationary distribution of the MDP. To resolve this latter issue, we will derive convenient characterization for admissibility.
Call π (-Is) admissible if the Markov Chain with transition probability p defined for Assump- tion is positive recurrent, and denote Wr as its stationary distribution. Define the set 0: Eisism, w(li - 1)m, + Eisssmm Eisism, w((k 1)m, + +()k(i)k,,
W
V1 < is m,, Eisism. Eisigm. wlli - 1)ma + + =1) The following provides a characteriza- lion of the set of admissible w:
Lemma 1. For any admission policy n, Wx E W. For any w E W, Tw with Tee (a j|s i) w((i - 1)ma + 5)/ (Era w((i- 1)ma + k)) is an admissible policy.
In other words, optimizing over the set of admissible policies is equivalent to optimizing over the set of stationary distributions. The latter is much more tractable thanks to the linear structure of W. In practice, we will use Wr W (w 2 nf for some small r > to ensure closedness of the set (our experiments use 17 10-9).
Algorithm 1 describes Q-OCBA. In our experiments shown next, we simply use two stages, i.c., K= 2. Finally, we also note that criterion like ( can be modified according to the decision goal.
6

---

Under review conference paper at ICLR 2020
For example, if one is interested in obtaining the best estimate of x", then it would be more beneficial to consider min ox We showcase this with additional experiments in the Appendix.
Input: Number of iterations K, length of each batch [Ba]i initial exploration policy To:
Initialization: k = 0; while h & K do
Run Tı for Bu steps and set k = l: + 1;
Calculate PB., Bnn,B, RR R.B, Br and WB. based on the B& data points collected
Apply malue-iteration using PB. and BR to obtain QB.
Plug the estimates PB., R. and QB, into (7) to solve for the optimal w/
Set (a = j|s = -) = wx ((i - 1)mo + j)/ Exs wx((i 1)m, + l);
end
Algorithm 1: Q-OCBA sequential updating rule for exploration
Note that 7 is equivalent to min, maxes maxjeAAjia (1) Σ,,e Ci,(s, a)/ws, subject to w E Wn. where Csyl8, 8, a)*s are non-negative coefficients. Based on the closed-form characterizatio ion of Σ in Theorem (sy(sa)'ss can be estimated with plug-in estimators using data collected in earlier stages.
5 NUMERICAL EXPERIMENTS
We conduct several numerical experiments to support our large-sample results in Sections 3 and demonstrate the performance of Q-OCBA against some benchmark methods. We use the RiverSwim problem in (Osband et. al., 2013) with m, states and two actions at each state: swim left (0) or swim right (1) (see Figure D. The triplet above each represents i) the action, 0 or 1, ii) the transition probability to the next state given the current state and action, iii) the reward under the current state and action. Note that, in this problem, rewards are given only the left and right boundary states (where the value of TL will be varied). We consider the infinite horizon setting with
y 0.95 and p = [1/m....... 1/m,]".
(1,0.7,0)
(1,0.6,0)
(1,066,0)
(1,066,0)
(1,0.6,0)
(1,033,10)
(10.3.0)
(1.03.0))
(1.0.30))
(1.03,0)
(1.0.3.0)
r0,1,))
(0,1,0)
(0,1,0)
(0,1,0)
(0,1,0)
(0,1,0)
(1,0.1,0)
(1,0.1.0)
(1,0.1,0)
(1,0.1,0)
(1,0.7,0)
Figure 1: RiverSwim Problem
We first demonstrate the validity of our large-sample results, We use a policy that swims right with probability 0.8 each state, i.c. x(|ss) 0.8. Tables [ and 2 show the coverage rates of the constructed 95% Cls. for a small m, = 6 (using Theorem and Corollary [ and large the Appendix) respectively. The latter case uses a linear interpolation ... 28, 3I.. All coverage rates are estimated using 10x independent experimental with So = {1, ...,.
m, = 31 (using Theorem
repetitions (the bracketed numbers the tables show the widths of 95% CI for the coverage estimates). For the Q-values, we report the average coverage rate over all (s, pairs. When the number of observations n is large enough (2 3 x 10a for exact update and 2 10" for interpolation), we see highly accurate CI coverages, i.c., close to 95%.
7

---

Under review conference paper at ICLR 2020
Table 1: Exact tabular update
Table 2: Approximate value iteration
72
10a
3 x 10*
5 x 10a
π2
10a
10
10
Q
(077()
(..00)
0.96(0.01)
Q
(.53()
0.95(0.01)
(0.00)
(077()
(.93(0.02)
0.96(0.01)
X
(.80()
0.94(0.02)
0.95(0.01)
Next we investigate the efficiency of our exploration policy. We compare Q-OCBA with K = 2 to four benchmark policies: i) e-greody with different values of c, ii) random exploration (RE) with different values of {1]ss), iii) UCRL2 (a variant of UCRL) with ē = 0.05 (Jaksch et al. 2010), iv) PSRL with different posterior updating frequencics (Osband et al.) 2013 I.c., PSRI mcans PSRL is implemented with episodes. We use m, 6 and vary Tr. from to 3. To ensure fairness, we use a two-stage implementation for all policies, with 30% of iterations first dedicated to RE (with warm start, i.e., the data are used to estimate the parameters needed for the
(1[ss) = 0.6) second stage. To give enough benefit of the doubt, we notice the probabilities correct selection for both UCRL2 and PSRL much worse without the warm start.
Tables 8 and 4 compare the probabilities of obtaining the optimal policy (based on the estimated Qn's), For e-greedy, RE, and PSRL, we report the results with the parameters that give the best performances in our numerical experiments. The probability of correct selection estimated using 10 replications of the procedure. We observe that Q-OCBA substantially outperforms the other methods, both with a small data size (n 10 in Table 3 and a larger one (n = 104 in Table D.. Generally, these benchmark policies perform worse for larger values of rz- This is because for small TL, the (s, a) pairs that need to be explored more also tend to have larger Q-values. However, rr. increase, there is misalignment between the Q-values and the (s, a) pairs that need more exploration.
The superiority of our Q-OCBA in these experiments come surprise to us. The benchmark methods like UCRL2 and PSRL are designed to minimize regret which involves balancing the exploration-exploitatinn trade-off. On the other hand, Q-OCBA focuses efficient exploration only, i.e., our goal is to minimize the probability of incorrect policy selection, and this is achieved by carefully utilizing the variance information gathered from the first stage that is made possible by our derived asymptotic formulas. We provide additional numerical results in Appendix B
Table 3: Probability of correct selection for different exploration policies, n 103
Fz.
0.2-greedy
RE(0.6)
UCRL2
PSRL(100)
Q-OCBA
0.95(0.01)
0.70(0.03)
0.44(00.3)
0.53(0.03)
0.87(0.02)
2
0.15(0.02)
0.29(0.03)
0.10().00)
0.330)
0.55(0.03)
3
0.00(0.00)
0.45(0.03)
0.21(0.02)
0.41(0.03)
0.84(0.02)
Table 4: Probability of correct selection for different exploration policios, n = 10
72
0.2-greedy
RE(0.6)
UCRL2
PSRL(100)
Q-OCBA
1
1.00(0.00)
0.95(0.01)
0.82(0.02)
1.00(0.00)
1.00(0.00)
2
0.55(0.03)
0.80(0.03)
0.52(0.03)
0.94(0.02)
1.00(0.00)
0.21(0.03)
0.94(..01)
0.75(0.03)
0.76(0.03)
1.00(0.00)
8

---

Under review conference paper at ICLR 2020
REFERENCES
Joshua Achiam, David Held, Aviv Tamar, and Pieter Abbeel. Constrained policy optimization. In Proceedings of the 34th International Conference on Machine Leorning- Volume 70, pp. 22-31. JMLR. org, 2017.
Eitan Altman. Constrained Markov Decision Processes, volune 7. CRC Press, 1999.
Jean- Yves Audibert and Sébastien Bubeck. Best arm identification in multi-armed bandits. In COLT-2304 Conference on learning theory-2010, pp. 13 p, 2010.
Craig Boutilier and Tyler Lu. Budget allocation using weakly coupled, constrained markov decision processcs. In Proceedings of the Thirty-Second Conference Uncertainty in Artificial Intelligence, pp. 52 61. AUAI Press, 2016.
Chun-hung Chen and Loo Hay Lee. Stochastic Simulation Optimization: An Optimal Computing Budget Allocation, volume World scientific, 2011.
Yinlam Chow, Mohammad Ghavamzadeh, Lucas Janson, and Marco Pavone. Risk-constrained reinforcement learning with percentile risk criteria. The Journal of Machine Learning Research, 18(1):6070 6120, 2017.
Jing Dong and Yi Zhu. Three asymptotic regimes for ranking and selection with general sample distributions. In Proceedings of the 2016 Winter Simulation Conference, pp. 277-288. IEEE Press, 2016.
Eugene A Feinberg and Uriel G Rothblum. Splitting randomized stationary policies in total-reward markov decision processes. Mathematics of Operations Research, 37(1):129-153; 2012.
Peter Glynn and Sandeep Juneja. large deviations perspective on ordinal optimization. In Pro- ceedings of the 36th conference on Winter Simulation Conference, pp. 577 585. Winter Simulation Conference, 2004.
Geoffrey J Gordon. Stable function approximation in dynamic programming. In Machine Learning Proceedings 1995, pp. 261-268. Elsevicr, 1995.
T. Jaksch, R. Ortner, and P. Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(Apr):1563 1600, 2010.
S. M. Kakade. On the sample complexity of reinforcement learning. PhD Thesis, University College London, 2003.
Dmitry Kalashmikov, Alex Trpan, Peter Pastor, Julian Ibarz, Alexander Herzog, Fric Jang, Deirdre Quillen, Ethan Holly, Mrinal Kalakrishnan, Vincent Vanhoucke, et al. Qt-opt: Scalable deep reinforcement learning for rision-based robotic manipulation. arXiv preprint arXiv:1806. 10293, 2018.
M. Kearns and S. Singh. Finite-sample convergence rates for Q-learning and indirect algorithms. In Proceedings of the conference on Advonces in neural information processing systems 11, pp. 996 1002, 1998.
Eric B Laber, Daniel J Lizotte, Min Qian, William E. Pelham, and Susan A Murphy. Dynamic treatment regimes: Technical challenges and applications. Electronic journal of statistics, 8(1): 1225, 2014.
9

---

Under review conference paper at ICLR 2020
Shie Mannor, Duncan Simester, Peng Sun, and John N Tsitsiklis. Bias and variance in value function estimation. In Proceedings of the twenty-fing firsttt-fsstttte international conference on Machine learning, pp. 72. ACM, 2004.
Shie Mannor, Duncan Simester, Peng Sun, and John N Tsitsiklis. Bias and variance approximation in value function estimates. Management Science, 53(2):308 322, 2007.
Rémi Munos and Csaba. Szepesvári. Finite-time bounds for fitted value iteration. Journal of Machine Learning Reseorch, 9MMay))815-857, 2008.
lan Osband, Daniel Russo, and Benjamin Van Roy. (More) efficient reinforcement learning via posterior sampling. In Advances in Neural Information Processing Systems, pp. 3003-3011, 2013.
Robert J Serfling. Approrimation Theorems of Mathematical Stalistics, volume 162. John Wiley
Sons, 2009.
A ADDITIONAL THEORETICAL RESULTS
In this section, we present additional results on large-sample behaviors for constrained MDPs and also estimations based on approximation value iteration.
A.1 CONSTRAINED PROBLEMS
We consider the constrained MDP setting for budgeted decision-making more recently safety-critical applications (Achiam et al. 2017 Chow et al. 2017). Suppose now we aim maximize the long-run accumulated discounted reward, V*(3) E 2 R(s,,, π (s;)) (o s), while at the same time want to ensure that a long-run accumulated discounted cost, denoted as (s) E| 2 (s))))s = s] which we call the loss function, is constrained by some given value i.e.,
(Boutilier & Lu
2016 and
max Σ (()) subject to E((s)((()
We assume data coming in like before and, in addition, that we have observations the incurred cost at each sample of (s, a). Call the empirical estimate of the cost P.... We follow our paradigm solve the empirical counterpart of the problem, namely to find a policy # that solves {8 by using (s) and (s) instead of (*()) and (s)(s), where V7 (s)'s and [: are the value functions and loss functions evaluated using the empirical estimates Pa.a Ac... Pn. We focus on the estimation
error of the optimal value (instead of the feasibility, which could also be important but not pursued here).
To understand the error, we first utilize an optimality characterization of constrained MDPs. In general, an optimal policy for (8) is a "split" policy (Feinberg & Rothblum 2012), namely, policy that is deterministic except that at one particular state randomization between two different actions is allowed. This characterization can be deduced from the associated LP using occupancy measures (Altman, 1999). We call the randomization probability the mixing parameter a", i.c., whenever this particular state, say Sr, is visited, action (s,) is chosen with probability a' and action a8,), is chosen with probability
a*. We then have the following result:
Theorem 3. Suppose Assumptions 0 and 3 hold and there is a unique optimal policy. Moreover, assume that there is no deterministic policy that satisfies Σ, L(s = Then we have Vn(V: V*) = N(O,E) as + 00, where of the following cases hold:
10

---

Under review conference paper at ICLR 2020
1. The optimal policy is deterministic. We then have ا Ev where Ev defined in Theorem 1
2. The optimal policy is determimistic, except at one state where a randomization between two actions occurs, with the mixing porameter a'. Denote the state where the randomization occurs by and two possible actions for St by (s,)) and az(s,), We have
(1 (1-pP") ) qv qqpp (1 1-Pp"' ) 10, OF .HH
= (1->ppm'--(C
,0, 1.
p² - -PP=)
ERCCP (I- 00, H. (I- ) qv p (1 - 11---- 10, G -HE
pT - -
where ΣR,C,P = Diag(W--ll DR. W W Dp) qv and qL are m, ddddimmnssinal vectors with qv()) and (s) (Pc(s, (c(s)))(s)) - ()) (ss) P(jss, az(s)) when = Sr, and (e(s) gL(s) = 0 when s & Sr,
(wn(s, a7 (s)) pn (n)(s,0(()))
TV" (())
(+1)²²
o7 (1)
G
x (-Ima,)
a (m,)²)
o (ma () (O(V''T) which an N- (ili)(==") ."...,, where af (1)T = >(5 (1))( ...... xz .....,,*"1l1
dimensional row vector, and Hy" and of (1) are defined similarly by substituting V with L.
Case 1 in Theorem 3 corresponds to the case where the constraint in S is non-binding. This effectively reduces to the unconstrained scenario in Theorem since a small perturbation of pn. lc, P does not affect fcasibility. Case 2 is when the constraint is binding. In this case, a" must be chosen such that the split policy ensures equality in the constraint, and when PR. Pc. P is perturbed the estimated a would adjust accordingly. Thus, in this case the estimation of V* incurs two sources of noises, one from the uncertainly of R, P that appears also in unconstrained problems, and one from the uncertainty in calibrating a that in turn affected by C,P, thus leading to the extra terms in the variance expression.
A.2 APPROXIMATE VALUE ITERATION
When the state space S is large, updating an m, X m. look-up table via P(.) can be computation- ally infeasible. Approximate value iteration operates by applying mapping M over TuR.P. In many cases, M My o M where S is dimension-redueing "inherit" mapping gm,ma + ma and M, is the "generalization" mapping "."."".. + mm that lifts back to the full dimension. By selecting "represenlative" subset. So C S with cardinality |Spl = m. & m,y MS is defined as M = (ifi:j)liess..ssssss where [ra]ier denotes the set of entries of x whose index E 1. In this setup, we define QM as a fixed point of the operator M o P(), and V (s) max. Qa (s, a). We also define Q S (QM.
the dimension-reduuced Q-value.
We derive largo-sample error estimates in this case. For this, we first assume there is a well- defined metric on S. To guarantee the existence of QM, we make the following assumption on the generalization map Mg:
Assumption 4. Mg is mar-norm non-expansion mapping in S, i.e,, [|, Mg(y)llo || - y VI, S.
We also need the following analogs of Assumptions and to M and Sq:
11

---

Under review conference paper at ICLR 2020
Assumption 5. For any state S, arg A Qa (s, a) is unique.
Assumption 6. For the Markov Chain with transition probability pr, the set of states {(s, So, a E A} is in the same communication class and this class is positive recurrent.
Let No = m. m. and Is. = {(i - 1),, +j:ie So. E A}. With Assumption 6 we denote PM
sub-matrix of the matrix ps that only contains with indexes in Is.. We also denote So(i) as the i-th element (state) in So- We define Q as the empirical estimator of QM built on observations. Then we have:
Mg is continuously differentiable, then vn(Q Theorem 4. Under Assumption and Q²) ((, E
0C, where
So (1 - -V, - VM, (V + + (f (11-VVM, )イ)
Mg is the Jacobian of mapping Mg. W D Dē are No x No diagonal matrices with W ((i 1yma j. (i 1)ma j) w ()))(i),)), Doo ((i 1)ma + J, (i 1)m = D ((i
1)ma j. 1)ma + J = (V E VM.
Assumption f is generally satisfied by "local" approximation methods such linear interpolation,
k-nearest neighbors and local weighted average GGordon 1995). In all these cases, VMg in Theorem is actually a constant matrix.
B ADDITIONAL NUMERICAL RESULTS
This section reports additional numerical experiments. Sections B.1 present further results on the estimation quality of Q-values, V*and x". Section B.2 provides additional results to demonstrate the efficiency of our proposed exploration strategy.
B.1 STATISTICAL QUALITY OF INTERVAL ESTIMATORS
In this section, we provide additional numerical results about Tables 1 and 2 in the main paper. For Q-values in Table 1 of main paper, we only report the average coverage rate over all (s, a) pairs. Table 5 presents the coverage rates for cach individual Q-values. It also provides the coverage rates for the value functions and x" where X" is the uniformly initialized value function, i.c. P p= ==/mm,,,.... 1/m,)²" We use RE with T1lss) 0.5 our exploration policy. We see that the behaviors of these individual est intatts are largely consistent. The coverage rales all converge to the nominal 95% the number of observations n increases. Moreover, the coverages for the individual Q's, V*'s and the averages of these quantities are similar at any given n. Specifically, when n = 104, the coverages are all around 77% 78%, when
10 they all around 93%, and when n = x 10s they are all very close to 95%. Those suggest a sample size of 5 x 10 (or lower) enough to elicit asymptotic results in Thcorem 1 and Corollary 1 in this problem.
12

---

Under review conference paper at ICLR 2020
Table 5: Coverage for Q(s, a), V and x" values using exact tabular update
n
10
3 x 10
5 x 10
Q(L,0)
0.773(0.026)
0.956(0.013) (.930)
Q(11))
0.773(0.026)
0.956(0.013) 0.930(0.016)
Q(2.0)
0.773(0.026)
0.956(0.013) 0.930(0.016)
Q(2.1)
0.771(0.026)
0.955 0.930)0.016)
Q(3.0)
0.771(0.026)
0.930(0.016)
0.955(0.013)
Q(3.1)
0.771(0.022)
(.957(0.013) (.916))
Q(4.0)
0.771(0.002)
(.926))
0.957().012)
Q(4.1)
0.775(0.026)
0.952 0.934(0.0115)
Q(5.0)
0.775(0.026)
0.934(0.015)
(.952)
Q(5.1)
0.775(0.026)
(0.05))
(.954
Q 0)
0.775(0.026)
0.954(0.013 0.935(0.015)
Q(6.1) 1)
0.750(0.026)
0.920(0.017)
0.950(0.014)
Average of Q
0.77I(0.022)
0.956(0.013) (0.016)
(*(1)
0.773
0.930(0.016)
0.956(0.013
(-(2)
0.702(0.026)
0.930(0.016)
(0.553
V²(3)
0.774(0.002)
(.926))
0.957(0
(4(4)
0.776(0.026)
0.952 0.934(0.0155
(5)
0.772
0.954(0.013) 0.985(0.015)
(*(6)
0.752(0.027)
0.920(0.017)
0.950(0.014)
Average of V
0.769(0.026)
0.955(0.012) (.929))
X"
0.772(0.026)
0.958(0.012) (.903().011)
Tables 6 and compare the CT coverage rales when the state space is large, i.e. m, = 31, using RE with different values of ((|ss,, i.e, ([(ss) 0.8, 0.85, and 0.9. Compared to exact update, the coverage convergence for approximate update appears generally slower. Specifically, comparing Tables 5 and G that use the same RE with r(lss)= 0.8, see that the coverages of Q's and V for approximate update are only around 23% - 25% when n = 10 whereas they 77% 78% for exact update. Also, while the nominal coverage, i.c., 95%, is obtained when n = 5 x 10a in the exact update for all studied quantities, this sample size is not enough for approximate update, where il appears we need to be of order 10" to obtain the nominal coverage.
the averages
Furthermore, Tables 7 and g show that the rates of convergence to the nominal coverage are quite different for different values of π (1]s)ss. The convergence rate when T (1[s)= = 0.85 seems to be the fastest, with the coverage close to 95% already when n = 10a. On the other hand, when <{]ss) 0.8, the coverage close to 95% only when is as large as 10?, and when π π () = 0.9, even = 10 is not enough for convergence to kick in. We also see that, when the coverage is very far from the nominal rate, discrepancies can show up among the estimates of Q, V* and x" For example, when (1]ss) = 0.8 and coverage x" as low as 1%, and when x (1[s) = 0.9 and n 107, the coverages of Q and V* are around 75% 77% but that of x" is only 29%. However, in settings where the coverage is close to 95%, all these quantities appear to attain this accuracy simultaneously in all considered cases. These caution that coverage accuracy can be quite sensitive to the specifications of the exploration policy. Nonetheless, the convergence behaviors predicted by Theorem 1, Corollary and Theorem 4 all observed to hold.
104, the coverages of Q and V* are around 23% 25% but the
13

---

Under review conference paper at ICLR 2020
Table Linear interpolation in approximate value iteration with (1(ss) = 0.8
72
10a
10
10
10'
Average of Q
0.23(0.01)
(..03)
0.92(0.02)
0.95(0.01)
Average of V
0.25(0.01)
0.56(0.02)
0.93(0.01)
0.95(0.01)
X" coverage
(0.1()
0.35)0
0.94(0.02)
0.94(0.02)
Table 7: Linear interpolation in approximate value iteration with [(|ss) 0.85
N Average of Q
10a
10
106
10
(..02)
0.95(..01)
0.95(0.01)
0.95().01)
Average of V*
(.50()
(0950
0.95(0.01)
0.95(0.01)
X" coverage
0.80(0.03)
0.94(0.02)
0.95(0.01)
0.94(0.01)
Table 8: Linear interpolation in approximate value iteration with (1|ss) = 0.9
10a
10a
10c
107
Average of Q
0.31(
(.49)
0.67(0.01)
0.75(..02)
Average of V*
0.37(0.01)
0.54(0.01)
0.71(0.01)
0.77(0.02)
X" coverage
0.25(0.03)
0.30(0.03)
0.28(0.02)
0.29().03)
B.2 EFFICIENCY OF EXPLORATION POLICIES
In Q-OCBA, our sccond-stage exploration policy derived by maximizing the worst-casc relative discrepancy among all Q-value estimates. If one is interested in obtaining the best estimate of x" (i.e., the optimal value function initialized at a distribution p), then would be more beneficial to consider solving
min wEW, X
(9)
to derive the optimal second-stage exploration policy The (recall Lemma 1). The motivation is that by doing so we would obtain C1 for x" as short as possible.
Table compares the 95% CI lengths and coverages for this exploration policy with other benchmark stralegies, for rr. ranging from to 3. For each rı,, show the averages of the coverages and CI lengths of Q estimates among all (s, pairs, and also the coverage and CI length of x" estimates. Note that our strategy intends shorten the CI lengths of x" estimates. Like our experiment in Section 5 in the main paper, we use a total observation budget = 10a, and devote 30% to the initial stage where RE with x(1[s) = 0.8 is used estimate the parameters used to plug the critcrion to be optimized in the second stage. For convenience and the consistency of terminology, we continue to call our procedure to attain criterion (9) Q-OCBA. We compare this with pure RE and e-greedy, with ranging from 0.01 to 0.2.
Table ssoows that our budget is enough to achieve the nominal 95% coverages for both the Q-values and x" using all strategies, which is consistent with the conclusion from Theorem 1 and Corollary 1. However, Q-OCBA leads to desirably much shorter CI's generally, with the shortest CI lengths in all settings and sometimes by big margin. For example, when r 2, the CI length derived by Q-OCBA is at least 80% less than those derived by all the other methods. We also observe that Q-OCBA performs much more stably than RE and c-greedy, the latter varying quite significantly
14

---

Under review conference paper at ICLR 2020
for different values of rL. When rL 1, e-greedy with e 0.01 can perform almost as well as Q-OCBA, with both CI lengths for Q being 2.45 2.46 and for x" being 2.41 - 2.42. But when ry = 2, e-greody with the same 0.01 cannot even explore all (s, a) pairs. The situation worsens when rr. = 3, where none of the considered values of é can explore all (s. pairs. This observation on e-greedy consistent with Table in the main paper where we consider the criterion using the probability of correct selection. Regardless of using that or the current criteria, the performances of e-greedy depend fundamentally on whether the (s, a) pairs that need to be explored more also tend to have larger Q-values. Note that when changing TL, the corresponding changes in the Q- Davaue would change the exploration "preference" for 6-greedy. However, as the underlying stochasticity of the system does not change with rL: the states that need more exploration remain unchanged. This misalignment leads us to observe quite different performances for e-greedy when varies. Lastly, again consistent with the results on the probability of correct selection shown in Table 3 of the main paper, we observe that Q-OCBA outperforms pure RE in all cases in Table 5, with at least 40% shorter CI lengths for the X" estimates. This is attributed to the efficient use of variance information in the second stage of Q-OCBA.
Table 9: Length of CT comparison for different exploration policies
0.2
c= 0.1
0.01
T(
0.8
Q-OCBA
Tr.
Q Coverage
0.94(0.05)
0.97(..03)
0.97().03)
0.97(0.01)
0.96(0.04)
Q CI length
3.86(0.16)
2.73(0.09)
2.46(0.03)
3.85(0.05)
2.45(0.03)
X Coverage
0.94(0.05)
0.97(0.03)
0.98(0.03)
0.97(0.01)
0.95(0.04)
X CI length
4.11(0.04)
2.86(0.01)
2.42(0.01)
4.10(0.01)
2..1
F1. 2
Q Coverage
0.98(0.01)
0.96(0.01)
NA
0.97(0.01)
0.97(0.01)
Q CI length
2.25(0.14)
2.72(0.17)
NA
1.84(0.11))
0.32(0.02)
X coverage
0.96(0.01)
(.902.
NA
0.96(0.01)
0.96(0.01
CI length
2.69(0.02)
3.20(
NA
2.20(0.01)
0.37(0.01)
TL
Q coverage
NA
NA
NA
0.97(0.01)
0.97(0.01)
Q CI length
NA
NA
NA
0.74(0.06)
0.40(0.03)
X" coverage
NA
NA
NA
0.95(0.01)
0.96(0.01)
CI lengthh
NA
NA
NA
0.9T(0.01)
0.49(0.01)
"NA means that some (s, a) pair has never been visited.
C PROOFS OF MAIN RESULTS
In this section, we present the proofs of the main results. In the prools, we shall treat P as an Nm, -imeensnnii vector following the index rule: P(i 1)N + (j - 1)m, + k) = j(
Proof of Theorem 1 Define F(Q', r', P') a mapping from R x R Nm R.N Specifically,
F(Q',r' r', P') 1)ma + = Q'(( - 1)mm + 5) - ((i 1)ma + +
Σ Pi 1)N + 1)m, + k) gv (Q')
18k5m,
for 1 $ii m, and 1 $ may where gu (Q') max; ((: 1)m, + 1), for 1 < k: S m..
15

---

Under review conference paper at ICLR 2020
By Assumption 2 there exists an open neighborhood of Q, which we denote Q2 such that VQ' E S arg max; Q' - 1), +) is still unique for cach 1 S i S my. Then, for each < h I max I=( has all its partial dcrivatives exist and continuous. This implics that F(Q', ,', Pt) continuously differentiable in Z RR x R Nm.
Denote the partial derivalives of F as
OF aQ' P')
OF OF OF 8Q' Ôr OP
Note that OF is an N x N matrix. Denote its element at the ((i 1) + + row, ((k 1)ma + +()tth 807
column by OF 1mm
Then we have
1)mat! ()-mmatt
0P OF 11
1 ( (,)= - 7 1)N + (j - 11mm + k)
0Q (k- 13m4
x (Q' - 1)ma + +1) max Q' ((k: 1)mb + u)
Putting all the elements together, we have
OF aQ'
I yp',
where Pr is an N N matrix with
P'((i P 1)ma j. (k- 1)ma +1)
P'( - 1)N (j 1)m, + k) (1(Q + () max Q'(( ((k-1)nn 1)ma + u)),
for 1 sis m. 1 S 1a S k m,,1 SIS ma.
Since all rows of Pr sum up to one, F can be interpreted as the transition matrix of a Markov Chain with state space {(i.j) : S my S S ma). Note that OF is invertible for any Q' Ω. aQ7
We can then apply the implicit function theorem to the equation F(Q, UR, P) = 0. particular, there exists an open set U around μR x P R RNM, and unique continuously differentiable function Φ: U + R.W such that for any r' x X EU
0(UR, P) Q
F(o(r', P'),t', P') = 0.
In addition, the partial derivatives of satisfy
de
0F [0Q']
OF OF Or Dp
VoluR, P) a(r, P')
M'ERR
Q'=Qr'=px,P''
It is also easy to verily that
0F
1NNN.
Ör'
P'=
We also note that
3FG-m1mmt
? max Q((v 1)m, + u)1 (Is =.j=1)
aP (k- ()--1)++(1111 (1-1)m--1 -0 P'
VV* (k.
16

---

Under review conference paper at ICLR 2020
for 1 Si S mai 1 S S maid S ma,d SIS ma, and S S ma. Then
(V*)T
C OF
(V*)T
OP
Q'= Qr
(V*)²
which is an N x Nm, matrix.
Next, for
Eision a1
pn, ((i
1) +
Eisign (8 = 1,
Eisien re(s a+) -1,0 = j)
w(li 1)ma + j
w(li 1) + +j)n
Eisisn 1(s i, = j)
and
Pa((i - 1)N ( (j-1)m, + k))
Eisisn 1(st = i, = j. s/ at) = k)
Eisign 1s; i, 5)
Eigign 18t i, = j. (8 at) = k))
w((i 1)ma + +J)
w(li 1)mL j)n
Eisisn 1s; i. j)
by Assumption 1 3 and Slutsky's theorem, we have
PRR, Px] - [ P| + 0 a.s
and
Vn Pal [UR, PI) NO, ER.,)
(10)
W-1 DD
where ER,
and
0
Dp
Σr.,1 w(Um, +1)
EP. w/ 151
Dp
Pm
( 1)m tmm))
which is an Nm, x Nm, matrix. By the continuous mapping theorem, we have MPa.. Pw) - Hun, P) - 0 a.s. as n + 0o,
which implies Qn + Q a.s.. In addition, using the delta method, we have Vn(Q.. -Q) Vn(ølpnn, P.)) - 0(un, P)) NOO., VĀ(UR. PJER VolUR P)+) 00.
17

---

Under review conference paper at ICLR 2020
We also have
P)ER, P)T
W (I - [1 W- DR
0
[I, 11, - -ppp"
Dp
(I - 1-pp"r ) ) (W DR + CT Dp(C") )( - -
(I (I->P")) 1--7p""------- - - )-1)
Proof of Corollary 7 Define gv(Q): RN R
(v) (9) (Q), ................................ 9n, (Q)) (m.)......,(())
= (V* (1), V= (ma)),
which is continuously differentiable in open neighborhood of Q. Then we can apply the delta method to get.
Vn(Vz V²) = (n(ev((n)) gv (Q)) = NiO, (Q)(())
+ 00.
Note that (Q) is a m, x N matrix with Vgv (j - 1)m, + k) = =i== By (where "*" denotes a placeholder of some quan-
rearranging the index such that fa pr
tities), we have Vgv(Q) = [1,0,, DR Diag Di +), W = Diag(W*' ,*) and DQ Diig DF *). We also note that
Vgv (1
[T.0]
('pp"''
(p
0
[I,0]
0
i=0
Σ
7d (px*) y00 00= = [
7px )
==
Thus,
[I- - 7p= 1 W W- + Dol (1 (1-1p=')-1,000
(I -1->p"")-(w""">-- + DE 1((1 - -yp-"
Lastly, the asymptotic normality of Xx. follows from the continuous mapping thoorem.
We next establish the asymptotic normality for the estimated value function under a given policy न. In this case, the value function V satisfies a Bellman equation
v*(s) Σ un(s, a)F(a(s) + Σ a(aas) E (()))..))v*)))
Denote the the estimator of V by Væ+ In particular, V# is the fixed point of the corresponding empirical Bellman equation that replaces (UR, P) by (pR P.). We have:
18

---

Under review conference paper at ICLR 2020
Corollary 2. Under Assumptions 1 and 3
Vn(Vn n - -V ~00,
where
=
X' =( (I-7PB)-1, pa is m, ms transition matriz with Pa (i.j) Ea i, 1),
W is en ms x m, diagonal matrix with
(1, Σ グリル)² (i.i x(t
Ep. (7V*) + (i,ji)
Proof of Corollary Similar to the proof of Theorem 1 define F as a mapping from R x RN x NN,, R m
F*(V' r, (') = (s) Σ () -7 *tals)) Σ ('s('(ssa\VV'(s))
Note that F (V* pn, P) =, O, F is continuously differentiable and J pP is invertible. We thus apply the implicit function theorem. In particular, there exists open set U around PA X PE RN x RN,, and a unique continuously differentiable function o²: U + R such that
Φ" (PR. P) V
F ( ( P',,' P') =0
for any r' x P' E UR.
For the partial derivatives of Φ² have
a
1
1 F OF* Gr OP
0(r', P')
=
OV
p'=p
V=V*,
where
F
=I->P²
0V
V'=VE, P
(-11)T
0F
G* =
*(11))T
0r'
#(- (-|m,.)
and
(attz
H OP
(q T
(g )T
where (q.)T = -la #(mali)(V5))) which is an N-dimensional row vector.
19

---

Under review conference paper at ICLR 2020
Applying the delta method, we have
Vn(V V*) Volo (MR, Pa) - -0 P))
NOO, (UR, PUER. (MR, PJT) as n n- 00,
where
(UR P/ER, R VO (UR, P)"
WW-IDR DR
G 1)
0
(I (I->Pi)- G H
Dp
= (1 11->Pi5-(G" " (
and the conclusion follows.
Proof of Theorem Write the MDP problem in its LP representation
[l)(s)((s) ((8) 27Eee ((d)),,)VV(')), Va,a
max subject to
+
with the dual problem
max
Σ Sna E. Tea Ev P(s|s' a))s = =(ss), as Kz.a 2 0, Vs, a
subject to
The decision variables in the dual problem, Fs.a 's, in particular represent the occupancy mcasures of the MDP. If the MDP has non-umique optimal policies, the dual problem also has non-unique optimal solutions, which implies a degeneration of the primal problem. Degeneration here means that some constraints are redundant al the primal optimal solution (i.e., the corner-point solution is at the intersection of more than m, hyperplanes). Since the rows of the primal LP are linearly independent, we know that in this case, there are multiple (K' > 1) choices for the set of basic variables (u s at the optimal solution. When the coefficients in the intersecting hyperlanes perturb slightly along given direction, the objective value will change by a perturbation of the objective coefficients along a chosen set of basic variables off In other words, we can partition the set of directions U into subsets {Uk]ISkSK' such that, if the direction of perturbation of (P, pR), say u, lies in UR, then the LP optimal value perturbs by fixing the basic variables as vf. Denote G as the gradient vector corresponding lo this direction. If some of the Gf's are equal, we merge the corresponding Uy's into one partition set. Thus, have KP > distinct G and partition of U = Uicksk where Ug = {u : (R(P, μR) = G2), and De(P. denotes the gradient of (s)()((s) with respect to (P,)n) along the direction u.
Note that the argument so far focuses on the LP with objective value E, (s)) How- ever, can repeat the same argument for each V(s) by setting p(s) Eg. For any U and 8 E S, denote the directional gradient of V(s) with respect to P, by (()(), thus we can define the directional Jacobian of V with respect to P, as D.V((P, UR) (1),,,) D2 (PP, (P,)(,,)))s,,.
(PV(P, (M))))) which leads to K 2 (potentially larger than KP) distinct G3 's, where G& E (gMmx(Nmm+M)) and U = UUSASKUR is partitioned with
UR (u: DuV(P, G.). Define in = (Pr. P, (iRm--RRR/ UR)/ / VII.. - P1I2 1 pRll2. We have
K
1 -M v = G&1 (0n E ( P.ARR MR) + o - P. P.RR. - -RR)1)
20

---

Under review conference paper at ICLR 2020
Multiply vn on both sides and notice that
n = (Vn(P, - -P), Vn(jRR pR)) (tal///lvvii llvi(P P)I + lIvn(Aa, pR)l
is a continuous mapping of (VT(Pa - P), VT(RRR - -R)). By laking n - 20, we gel the result by the continuous mapping theorem.
Proof of Theorem 3 occupancy measure
We use the LP represenlation of the constrained MDP. Define vsaa as the
F8. Σ PPp((,
where Po denotes the distribution of Si's with initial distribution p. Then, Fa.o satisfies the LP
max
s.a (R(S, (8,,8,))ss, In
subject to
(11)
E. Tza - -7 EEs P(s|s' a)) p(s), as Fxa 20, V8, a
(This is the dual formulation in the proof of Theorem 2 with an extra constraint.) The objective and the first constraint correspond to the objective and constraint in the constrained MDP formulation. The second constraint can be doducod by a one-step analysis on the definition of occupancy measure. Once [11 is solved to obtain an optimal solution (2% it can be translated into an optimal policy
x
T (als)
E
Note that the number of structural constraints [I] m. +,, and a corner-point optimal solution has m, + basic variables. Moreover, by our assumptions, the optimal solution is unique and the LP is non-degenerate, so that perturbing the parameters "s(s, a), (C a), P(s|s', a) does not immediately imply an overshoot to negativity for the reduced costs of the non-basic variables. Now consider two cases depending on whether the first constraint is non- non-binding or binding. The first case corresponds to a deterministic optimal policy, i.e., for any 8, Tssa > 0 for only case a small perturbation of the parameters still retains the same basic and non-basic variables, and the derived perturbed policy still retains the non-binding first constraint. In this case, the analysis reduces back to Corollary 2
In this
In the second case, Tz,a for only one a, for all s except one state 8r, where we can have (x.) > O and 2sr.aj(s-) > 0 for two distinct actions (s,), as,). Again, perturbing the parameters retains these basic and non-basic variables. In particular, the first constraint remains binding in the perturbation, so that the perturbed optimal policy x² is still split at the same state and satisfies Σ, L.) (s) = Now denote the mixing parameter by a* := T"" (sr(s))) and so x" (a;(s,))s,) =1 a² By applying the implicit function theorem to the Bellman equation, there exists continuously differentiable function &r. such that L*
L=((s) (s) Ór P, a²). By applying the implicit function theorem again to the equation Σ, (()))r((cc P.a') = 7, we know a" a function of pR, P and a", the latter in turn depending on #C and P. It can also be viewed as a function of pR. Pe and directly. We use V VaR.P.PPV (pn, PC,, P) to denote the Jacobian of V with respect to png Pc, P when viewing V as a function of these variables. We also use V Vaa V*un, P, a²) to denote the Jacobian of 4a with respect to PR.PO, P, a", this time viewing V as function of ug, P.a".
continuously differentiable function of pC and P. Thus V can be viewed
21

---

Under review conference paper at ICLR 2020
We use similar notations throughout, and their meanings should be clear from the context. To facilitate derivations, we also distinguish the notation Vaf, which denotes the multi-dimensional Jacobian matrix, from Özf, which is used to denote the Jacobian when x is a scalar (1-dimensional),
TuR.e.PP (UR, Hc, VR P.a V (MR, P. a |4, NuRie, (pc, P)",
Pasee PV (un, P. x) + 0n (uR, P. 0. P. Nu (NC,, P) (12)
Differentiating
p='L"" (URP = 1
wC have
V PR. P (Ne, (,c,P,a") + 0a 1.= (Mc, P,a")V pR. pa (Mc, P)=0. =0.
By rearranging the equation, we have
D V Pa (uc, ()c, p Lx" (NC, P,a V NuRwe, (Nc,P,a")
Substituting this into
12 we get
VR.SO. (UR, uo, P) URRV P,a")
1 V' bb (Mo, P, (URR P,a')
p L (Mc,
Next, define an m,-dimensional vector ro by rc(s) Mc Then
o L" (uc,P,a") pr L (rc, "(O,.ro(a")) (0xr p (A"))"IT
Note that (I - - =rc. By applying the implicit function theorem, have
I. (uc, P,a')= -1 -1- 1,
L T
QL
TT
= (I - -pp -1-
where di, a vector with (f pR(S ai (s+)) (R(s,,aa(s))) (s())), of (m, + (st 1)m, + 5) P(jlsr, P(ils,,aiss.)) P(ilsr, a)()))) for 1 < S ma and (1) = for any other index i.
Similarly, we can define FR by TR(s) Ex ( j)m (j]s}, and we have
0, V (nR, P,a') (1 7m ạv
The derivation of V P PV (UR, P, x²) and V PRR.E.PP p L (ne, P.a*) follows exactly the same line of analysis as how we derive G and Hy in the proof of Corollary 2
Proof of Theorem 4 Denote
L R.:: Pals. PRR. ((i - 1)m, + +J), P, 1)N (j - 1)m, + k)) 13)ses Is..m.
22

---

Under review conference paper at ICLR 2020
and
[pn. pls. = (pn((2 1)m +)), - 1)N + (j 1)m, + k5ssss.s
By Assumption D have
W-1 So
VnlliRn Palso - lun: Pls.)= (N (n,,ss) where ER,P.S. =
D2
Notice Ma o M o o An..P. only involves random variables [āRaa, Pals.- Changing the distribution of [ Palsis, will not change the distribution of QA, We can thus assign auxiliary random variables AR., and Pr for all & So, 13 S ma: 1 S k S my. In particular, we define independent random variables for cach i & So by letting
(R 1) + 2 Vn N(uR(( - 1)ma + 1),
Pa 1)N + (j 1)m, +k) 2 -N(P((i- 1)N + (j 1)m, + k),
By doing so, we extend the ms ma dimenssioall random variable [A Pals, an m,m, m,ma-diment dimenssiiai random variable linn.. Pn]s and
= (O ER.P,s where ER,P, = ER..SS.
Vn((PRR, Pals -
1
Similar to the proof of Theorem define
F P)= Mg M o Tx)')(QQ))
By Assumption 4 My is max-norm non-expansion. Then, Mg o M is also max-norm non-cxpansion,
implying that V (Mg ) has all its eigenvalues less than or equal to 1. Thus,
FF PM(Tr.P((Q))L eQ'
have (M MR. = O. O. By Assumption 5 there exists a ,nn neighborhood las around (Q Pn, P), such that FMr continuously differentiable on Qas. Then, applying the implicit function theorem, have that there exists open set EM ΩM and continuously differentiable mapping ΦM on EM, such that ΦM (HR, P) = QM and
is invertible. By Assumption
TFMM aQ'
OFM OFM
VOM P)
Ord
OP
Using the delta method, we have
V QM) = NO0 VoM(Un, P) P)))) NO0 M
Proof of lemma 1 For any given policy x, by the balance equation for Markov Chains, its induced
stationary distribution w, satisfies
wx ((k: 1)m, I)P(ils a I)z(a j|s i) w. ((i 1)ma j) Σ k.
23

---

Under review conference paper at ICLR 2020
for any i E 8,j A. Summing up across j's for each have
Σ wr(li 1)ma +)
ΣΣ wn - 1)m, + P)ilsss = k. = ()=
Rd
Σ
w=((h - 1) + - 1)
On the other hand, for any w in W, Tw satisfies
Σ
w((k 1) + P(ils = k; a = () 1 j j/b = i)
kd
Σ w((k 1) + +iP(iss = k,a 1)vo((i 1)ma + + Σ wlli - 1)ma + u)
k,
Σ w((i 1) + w)w((i - 1)m. + 5)/ w(((
Ew((i - 1)mo + u) w((i 1)mo + j)
for all i E S. Thus, w is the stationary distribution of transition matrix pm.
24


Reviews:
[{"review_id": "rygsIq2CYS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper studies the inference problem of reinforcement learning. With a given exploration policy that satisfies some strong property to collect n data, the paper studies the distribution of the estimated optimal value function and Q-function when n goes to infinity. Both unique and non-unique optimal policy cases are studied. The non-unique case has a very different behavior as it is no longer Gaussian. The paper then uses these estimations to design a method that better explores and proposes a method Q-OCBA. Experiments were performed to compare this method with previous algorithms, e.g., UCRL.\n\nThe inference results for the Q-function is definitely important and will be useful for the community. But the authors should not ignore all the finite-sample bound results in their related work section, especially for those who achieving minimax rates. For instance: \nMG Azar, I Osband, R Munos, Minimax regret bounds for reinforcement learning, 2017\nMG Azar, R Munos, H Kappen, Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model, 2013\nA Sidford, M Wang, X Wu, L Yang, Y Ye, Near-optimal time and sample complexities for solving Markov decision processes with a generative model, 2018\nA Agarwal, S Kakade, L Yang, On the Optimality of Sparse Model-Based Planning for Markov Decision Processes\n\nPlease also see references therein. You can derive an inference result for the generative model as well. \n\nMore comments:\n* The assumption on exploration policy is quite restrictive. It essentially says the bound does not hold if the MDP is not communicating. However, the Q-function is still well defined.\n* The comparison to UCRL and other exploration-based method is not fair. In these results, the probability of picking \"the\" optimal policy is not important. Also, picking the correct action is not feasible if the problem is more complex. It is my understanding that your algorithm has a much larger regret due to that it requires to sample from every state.\n* What about finite horizon MDP?\n\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "ryeT97XIKH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Efficient Inference and Exploration for Reinforcement Learning\n================================================================\n\nThis paper presents a pure-exploration algorithm for reinforcement learning.\nThe approach is based on an assymptotic analysis of the Q-values, and their convergence to central limit distribution.\nUsing this analysis, and under specific assumptions, the algorithm outperforms existing algorithms for exploration.\n\n\nThere are several things to like about this paper:\n- Many existing analyses for efficient exploration are all based around more-of-the-same concentration bounds, which end up being quite messy and un-elegant. This approach based on central limit theorem appears to be more insightful and cleaner and I think there is something nice about that!\n- The proposed algorithm is reasonable, for the setting in question, and the experimental results show that it outperforms benchmark exploration algorithms in this setting.\n- The general structure of the paper, quality of writing and technical rigour appears to be of good standard... although I did not check all technical details carefully. [The paper is 24 pages long and we have many reviews]\n\n\nHowever, there are also some significant places where this paper falls short:\n- The problem setting that the authors consider is really not typical of the \"exploration\" problem in RL... I'm not talking about the fact that this is a \"pure exploration\" algorithm (that's fine), but instead that Assumption 3 is really not a good model for the types of problems that are \"hard\" for exploration in RL! For example, in the RiverSwim problem choosing an exploration policy = 0.8 right is essentially saying that you've already solved the hard part of the problem. Note - I am a little bit confused about the experiments in Tables 3 and 4, here it seems that you start with a pi(1|s)=0.6 which again feels like a cheat...\n- Would it be possible to compare this algorithm in a more like-for-like standard RL setting, perhaps using the standardised bsuite https://github.com/deepmind/bsuite (the \"deep sea\" problems might be of particular interest here.)\n- Alternatively, I can imagine a future version of the paper being more upfront about this deviation from the \"standard\" setting and highlighting that this is a special-type of result quite different from typical exploration in RL.\n- I'm not sure that this sort of paper is well-served by a conference like ICLR... certainly there seems very little of \"learning representation\" in this discussion of Tabular RL. That would sort of be OK if the paper made nods to how these *insights* could carry over the deep learning or at least RL with (linear) function approximation... I don't see much of that.\n\n\nOverall I do think this is an interesting paper, with a novel approach to pure exploration in tabular MDPs under specific assumptions.\nHowever, I'm not sure that this paper is well-suited to ICLR and I have some concerns about whether it really does address the sort of \"exploration\" problem in RL that one might expect.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "Sklmiy_6FH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper studies the asymptotic properties of action value function $Q$ and value function $V$. Specifically, the authors assume that we can collect $n$ data points $\\{(s_t,a_t,r_t(s_t,a_t),s_{t+1})\\}_{t=1}^{n}$. Based on the collected data, the authors calculated the sample mean of the unknown reward function $\\widehat r_n$ and transition probability $\\widehat{P}(\\cdot|s,a)$. They further defined an estimator $\\widehat Q_n$, which is the fixed point of the empirical Bellman operator $\\widehat{\\mathcal{T}}_n$ derived from $\\widehat r_n$ and $\\widehat P_n$. The authors proved under certain assumptions that $\\widehat Q_n\\rightarrow Q^*$ almost surely. Based on this argument, they also derived a similar convergence of value function $\\widehat V_n$ in distribution. Confidence intervals can also be established based on these results.\n\nThe proof of convergence in distribution is established based on the following idea: $\\widehat r_n$ and $\\widehat P_n$ converge to $r$ and $P$ by central limit theorem. By examining the Jacobian matrix of $\\widehat{\\mathcal{T}}_n$ with respect to $\\widehat Q$, it is found that the implicit function $\\widehat{ \\mathcal{T}}_n \\widehat Q -\\widehat Q=0$ can be solved in small neighborhoods of $\\widehat r_n, \\widehat P_n$ and $\\widehat Q_n$ as\n$$\n\\widehat{Q}_n = \\phi(\\widehat{r}_n, \\widehat P_n) \\qquad\\text{(implicit function theorem)}\n$$  \nThen by Slutsky theorem, $\\widehat Q_n = \\phi(\\widehat r_n, \\widehat P_n)$ also converges to $Q^*$ in distribution. The proof is straightforward and easy to follow. However, I have some concerns about the above analysis.\n\n1. The data $\\{(s_t,a_t,r_t(s_t,a_t),s_{t+1})\\}_{t=1}^{n}$ are collected by executing a fixed policy for n steps, which means the data points are not i.i.d. Therefore, the convergence of  $\\widehat r_n$ and $\\widehat P_n$ by central limit theorem may not hold ground, which further leads the later proofs potentially problematic.\n\n2. The $\\phi(\\cdot,\\cdot)$ function in implicit function theorem only exists in neighborhoods of $\\widehat r_n, \\widehat P_n$ and $\\widehat Q_n$. It is unclear from the current proof that $\\widehat Q_n$ fall into the same neighborhood of $Q^*$. Therefore, it needs to be justified that the limit point is $Q^*$.\n\n3. Even for the empirical estimator $\\widehat Q_n$, it is still the fixed point of $\\widehat{ \\mathcal{T}}_n$, which is hard to compute or solve. Thus Algorithm 1 may be inefficient in practice.\n\nOther comments:\n\nThe font and margin of this paper does not conform the format requirement of ICLR.\nWhat is $\\sigma_R(i,j)$ in Theorem 1 and Corollary 1? It seems to be undefined.\n\nI found it hard to read when the authors vectorize all the matrices and tensors to $N$ dimension vectors and $N\\times N$ matrices. In particular, the rearranged notations such $\\mu((i-1)m_a+j)$, $\\tilde P^{\\pi}((i-1)m_a+j,(i’-1)m_a+j’)$ are much more complicated that $\\mu(i,j)$ and $\\tilde P^{\\pi}(i’,j’|i,j)$. Similarly, the mapping $F(Q’,r’,P’)$ defined in the proof of Theorem 1 can be represented by the Bellman operator $\\mathcal{T}$ defined on page 3. \n\n====post rebuttal==\nI read other reviewers' comments and the author's response. I do not think the authors have addressed all my concerns. I will keep my rating. ", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper examined a pure exploration method for efficient action value estimates in tabular reinforcement learning.  The paper is on the theoretical properties of value estimates in the large sample regime.  The method is shown to outperform baseline algorithms for this task in tabular reinforcement learning.

The reviewers were divided on the merits of this work.  The use of the central limit theorem was viewed as elegant, and the results were thought to be potentially useful.  However, the reviewers several limitations.  They found the assumption of a communicating MDP to be overly restrictive (reviewer 1).  The algorithm may be computationally inefficient (reviewer 2).  The nature of "exploration" in this work is not the conventional meaning in reinforcement learning (reviewer 3).

The paper is not yet ready for publication at ICLR.  The theoretical results do not clearly convey insights for reinforcement learning with function approximation, and the reviewers are also not in agreement that the current results are applicable to a general MDP setting.
Decision: Reject