Confident Approximate Policy Iteration for Efficient Local Planning in $q^\pi$-realizable MDPs
Authors: Gellért Weisz
András György
Tadashi Kozuno
Csaba Szepesvari
Venue: NeurIPS 2022 Accept (2022)
Keywords: Approximate Policy Iteration
Reinforcement Learning
Planning
Markov Decision Processes
Linear Function Approximation
Sample Complexity

Abstract: We consider approximate dynamic programming in $\gamma$-discounted Markov decision processes and apply it to approximate planning with linear value-function approximation. Our first contribution is a new variant of Approximate Policy Iteration (API), called Confident Approximate Policy Iteration (CAPI), which computes a deterministic stationary policy with an optimal error bound scaling linearly with the product of the effective horizon $H$ and the worst-case approximation error  $\epsilon$ of the action-value functions of stationary policies. This improvement over API (whose error scales with $H^2$) comes at the price of an $H$-fold increase in memory cost. Unlike Scherrer and Lesner [2012], who recommended computing a non-stationary policy to achieve a similar improvement (with the same memory overhead), we are able to stick to stationary policies. This allows for our second contribution, the application of CAPI to planning with local access to a simulator and $d$-dimensional linear function approximation. As such, we design a planning algorithm that applies CAPI to obtain a sequence of policies with successively refined accuracies on a dynamically evolving set of states. The algorithm outputs an $\tilde O(\sqrt{d}H\epsilon)$-optimal policy after issuing $\tilde O(dH^4/\epsilon^2)$ queries to the simulator, simultaneously achieving the optimal accuracy bound and the best known query complexity bound, while earlier algorithms in the literature achieve only one of them. This query complexity is shown to be tight in all parameters except $H$. These improvements come at the expense of a mild (polynomial) increase in memory and computational costs of both the algorithm and its output policy.

Confident Approximate Policy Iteration for Efficient Local Planning in q" rreaalzzalee MDPs
Gellért Weisz
András György DeepMind, London, UK
DeepMind, London, UK University College London, London, UK
Tadashi Kozuno
Csaba Szepesvári DeepMind, London, UK University of Alberta, Edmonton, Canada
University of Alberta, Edmonton, Canada Omron Sinic X, Tokyo, Japan
Abstract
We consider approximate dynamic programming in y-discounted Markov deci- sion processes and apply it to approximate plamning with linear fulue-function approximation. Our first contribution is a new variant of APPROXIMATE POL- ICY ITERATION (API), called CONFIDENT A APPROXIMATE POLICY ITERATION (CAPI), which computes a deterministic stationary policy with an optimal error bound scaling linearly with the product of the effective horizon H and the worst- case approximation error & of the action-value functions of stationary policies. This improvement over API (whose error scales with 112) comes the price of an H-fold increase in memory cost. Unlike [Scherrer and Lesner 2012). who recommended computing non-stationary policy to achieve a similar improvement (with the same memory overhead), we are able to stick to stationary policies. This allows for our second contribution, the application of CAPI to planning with local access to a simulator and d' d-dimensional linear function approximation. As such, we design planning algorithm that applies CAPI to obtain sequence of policies with successively refindd accuracies on dynamically evolving set of states. The al algorithm outputs an ((ViIt)) -optimall policy after issuing O(dF* /&?) queries to the simulator, simultaneously achieving the optimal accuracy bound and the best known query complexity bound, while earlier algorithms in the literature achieve only one of them. This query complexity is shown to be tight in all parameters ex- cept H. These improvements come at the expense of mild (polynomial) increase in memory and computational costs of both the algorithm and its output policy.
Introduction
A key question in reinforcement learning is how use value-function approximation arrive at scaleable algorithms that can find near-optimal policies in Markov decision processes (MDPs). A flurry of recent results aims at solving this problem efficiently with varying models of interaction with the MDP. In this paper we focus on the problem of planning with a simulator when using linear function approximation. A simulator is a "device" that, given state-action pair query. returns next state and reward generated from the transition kernel of the MDP that is simulated. Depending on the application, such simulator is often readily available (e.g., in chess, go, Atari). Planning with simulator access comes with great benefits: for example, in a recent work, Waan et al. [021] showed that under some conditions is exponentially more efficient find near-optimal policy if a simulator of the MDP (that can reset to state) is available compared to the online case where learner interacts with its environment by following trajectories but without the help of simulator.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Our setting of offline, local planning considers the problem of finding a policy with near-optimal value at a given initial state So in the MDP. The planner can issue queries to the simulator, and has to find and output a near-optimal policy with high probability. The efficiency of planner is measured in four ways: the suboptimality of the policy found, that is, how far its value is from that of the optimal policy; the query cost, that is, the number of queries issued to the simulator; the computational cost, which is the number of operations used; and the memory cost, which is the amount of memory used (we adopt the real computation model for these costs). There are several interaction models between the planner and the simulator [Yin et al. 2022]. The most permissive one is called the generative model, or random access. Here, the planner receives the set of all states and is allowed to issue queries for any state and action. Coding a simulator that supports this model can be challenging, as oftentimes the set of states is computationally difficult to describe. Instead of random access, consider the more practical and more challenging local access setting, where the planner only sees the initial state and the set of states received result to query the simulator. Consequently, the queries issued have to be for a state that has already been encountered this way (and any available action), while the simulator needs to support the ability to reset the MDP state only previously seen states. A simple approach in practice to support this model is saving and reloading checkpoints during the operation of the simulator.
To handle large, possibly infinite state spaces, we use linear function approximation to approximate the action-valus functions q" of stationary, deterministic policies (for background on MDPs, see the next section). A feature-map is good fit to an MDP if the worst-case error of using the feature- map to approximate value functions of policies of the MDP is small:
Definition 1.1 (q" realiizzbbiil, uniform policy calue-funttion approximation error). Given an MDP. the uniform policy value-finction approximation ervor induced by a feature map s. which maps aattin pairs (s. to the Euclidean ball of radius L centered at zero in R.A over a set of parameters belonging to the d-dimensional centered Euclidean ball of radius B is
8 sus x 0:1 B (s,a)
inf sup 14 (s"(s - (v((s,))
where the outermost supremum is over all possible stationary deterministic memoryless policies (i.e., maps from states to actions) of the MDP
Our goal is to design algorithms that scale gracefully with the uniform approximation error & at the ex- pense of controlled computational cost. To achieve nontrivial guarantces, the uniform approximation error needs to be "small". This (implicit) assumption is stronger than the q rrealizzabilli assumption (where the approximation error is only considered for optimal policies), which Weisz et al. (22T]) showed an exponential query complexity lower bound for. At the same time, it is (strictly) weaker than the linear MDP assumption [Zanette et al. 2020], for which there are efficient algorithms to find near-optimal policy in the online setting (without a simulator) [Jin et al. 2020)) even in the more challenging reward-free setting where the rewards are only revealed after exploration (Wagenmaker ee al. 2022].
In the local access setting, the planner learns the features c(s, a) of a state-action pair only for those states that have already been encountered. In contrast, in the random access setting, the whole feature map (((,)) -), of (possibly infinite) size d|Ss (where and A are the state and action sets, resp.), is given to the planner as input. In the latter setting, when only the query cost is counted, Du al. (2019) and Lattimore et al. [2020] proposed algorithms (the latter working in the misspecified, >> O regime) that issue number of queries that is polynomial in the relevant parameters, but require a barycentric spanner or near-optimal design of the input features. the worst case, computing any of these sets scales polynomially in |S] and [M)], which can be prohibitive.
In the case of local access, considered in this paper, the best known bound on the suboptimality of the computed policy is achieved by CONFIDENT MC-POLITEX (Yin et al. 2022)] In the more permissive random access setting, the best known query cost is achieved by Lattimore et al. [2020]. Our algorithm, MAPI-QPI-PLAA
(given in Algorithm 3) achieves the best of both while only assuming local access. This is shown in the next theorem; in the theorem E as defined in Definition [.1 y is the discount factor, and r* and v are the state value functions associated with the optimal policy and policy π, respectively (precise definitions of these quantities are given in the next section). A comparison to other algorithms in the literature is given in Table [1 there the accuracy parameter w of the algorithms set to e, but a larger w can be used to trade off suboptimality guarantees for an improved query cost.
2

---

Theorem 1.2. For any confidence parameter ò E (0, 1], accuracy parameter w > O, and initial state Sp E S, with probability least 1 1 CAPI-QPI-PLAN (Algorithm 31 finds a policy n with
v (5())) v² (50) Ô ((s (l++w) -
(I)
while executing at most Ô (d(1 y) -) queries in the local access setting.
CAPI-QPI-PLAN is based on CONFIDENT MC-LSPI, another algorithm of Yin al. [2022). which relies on policy iteration from a core set of informative state-action pairs, but achieves inferior performance both in terms of suboptimality and query complexity. However, CAPI-QU PAPI-PPI-LLAN'S improvements come at the expense of increased memory and computational costs, as shown in the next theorem: compared to CONFIDENT MC-LSPI. the memory and computational costs of our algorithm increase by a factor of the effective horizon H Ó(1/(1 - y)), and the policy computed by CAPI-QPI-PLAN uses a dH factor more memory for storage and a d'H factor more computation to evaluate.
Theorem 1.3 (Memory and computational cost). The memory and computational cost of running CAPI-QPI-PLAN (Algorithm By are Ô the memory and computational costs of storing and evaluating the final policy outputted by CAPI- QPI-PIAN, respectively, are Ô (d² /(1 y)) and Ô (d)///((11)) ())
and Ô (d)))(( y) >>> - respectively, while
Next we present lower bound corresponding to Theorem 1.2 that holds even in the more permissive random access setting, and shows that CAPI-QPI-PLL trades of the query cost and the suboptimality of the returned policy asymptotically optimally up to its dependence on 1/(1 y):
Theorem 1.4 (Query cost lower bound). Let a E (0, (I-)) E (0, 0.08). y E [ 1], d 2 3.
0.05y
and & 2 O. Then there is a class M of MDPs with uniform policy value-function function approximation error at most E such that any planner that guarantees to find an a-optimal policy x (i.e., v* (sg) - v= (so) s a) with probability at least 1 1-6 6 for all M E M when used with simulator for M with random access, the worst-case (over M) expected number of queries issued by the planner is at least
max cxp (2
de²
d
a² y
a2 (a((1
(1-
If wu is set to for CAPI- CAPI-QPI-PLAY the first term of Eq. 2 implies that any planner with an asymptotically smaller (apart from logarithmic factors) suboptimality guarantee than Eq. (I) exccutes exponentially many queries in expectation. The second term of Eq. (2). which is shown to be lower bound in Theorem H.3 even in the more general setting of linear MDPs with zero misspecification
(E = 0), matches the query complexity of Theorem 1.2 up to an Ō( - bound implies that the suboptimality and query cost bounds of Theorem [.2) are tight up to logarithmic factors in all parameters except the 1/(1 ( -yde-deedeeeeeencee of the query cost bound.
?)) factor. Thus, the lower
At the heart of our method is new algorithm, which we call CONFIDENT APPROXIMATE POLICY ITERATION (CAPI). This algorithm, which belongs to the family of approximate dynamic pro- gramming algorithms [Bertsekas] | Munos 2003 2005]. is a novel variant of APPROXIMATE POLICY ITERATION (API) [Bertsekas and Tsitsiklis [996]: in the policy improvement step, CAPI only updates the policy in states where it is confident that the update will improve the performance. This simple modification allows CAPI to avoid the problem of "classical" approximate dynamic programming algorithms (approximate policy and value iteration) of inflating the value function evaluation error by a factor of H² where H = Ō (1/(1= - y)) (for discussions of this problem, see also the papers by |Scherrer and Lesner 2012 and Russo 2020). and reduce this inflation factor to H. A similar result has already been achieved by Scherrerr and Lesner [0012]. who proposed to construct a non- non-stationary policy that strings together all policies obtained while running either approximate value policy iteration. However, applying this result to our planning problem is problematic, since the policies to be evaluated are non non-stationary, and hence including them in the policy set we aim to approximate may drastically increase the error as compared to Definition I.] which only considers stationary memoryless policies.
While the improvements provided by CAPI allows CAPI-QPI-PIAAN to match the performance of CONFIDENT MC-POLIIEX in terms of suboptimality, is unlikely that simple modification of CONFIDENT MC-POLITEX would lead to algorithm which matches CAPI-QPI-PLAN'
3

---

Table I: Comparison suboptimality and query complexity guarantees of various planners (with the approximation accuracy parameter a set to s). Drawbacks are highlighted with red, the best bounds with blue.
Algorithm [Publication]
Query cost
Suboptimality
Access model
MC-LSPI Lattimore et al.
2020
0 s
(1-
(I-y)*
eva
random access
CONFIDENT MC-LSPI Yin et al.
2022
0
d²
<V (1->)*
local access
(1-)]
CONFIDENT MC-POLITEX Yin et al.
2022
LVVd 1-y
local access
(11--)>
CAPI-QPI-PLAN PLAN [This work]
0
d
svd
local access
(1-))
1:
T-y
performance in terms of query cost (see Table D: Both methods evaluate a sequence of policies at an (E)) accuracy each (requiring ((1=²)) queries, omitting the dependence on other parameters). (and CONFIDENT MC-LSPI) evaluates ( 1/e)) (again in terms of & only) policies to find one which Ō (optimalll,, CONFIDENT MC-POLITEX needs to compute (1//22) policies to achieve the same. As consequence, CONFIDENT MC-POLITEX only achieves O(1/=²) query complexity, and to match CAPI-QPI-PLANY Ó(1/²) complexity, one would need to come up with either significantly better policy evaluation methods (potentially using the similarity in the subsequent policies) much faster (exponential vs. square-root) convergence rate in the suboptimality of the policy sequence produced by CONFIDENT MC-POLITEX.
However, while CAPI-QPI-PLEE
The rest of the paper is organized as follows: The model and notation are introduced in Section 2 CAPI is introduced and analyzed in Section 3 Planning with -e-realizabiliiy introduced in Section 4 with
being built-up and analyzed in Sections 4.1 and [.2 In particular, the proof of Theorem 1.2 is given in Section 4.2 Several proofs are relegated to appendices, in particular, Theorem T.3 is proved and implementation details of CAPI-QPI-PI... PL.AN are discussed in
Appendix G while Theorem I.4 is proved in Appendix
2 Notation and preliminaries
Let = (0, 1. .) denote the set of natural numbers, =+ (1,2....) the positive integers. For some integer i, let [i] = (0. (o. 1). For E B. let [x] denote the smallest integer i such that i x. For positive definite
Rdxd and Rd, let ||x||e = x Vx. For matrices A and B, we say that A z B if A - B is positive semidefinite. Let be the d-dimensional identity matrix. For compatible vectors x. let (x. be their inner product: (x y Let Mi (X) denote the space of probability distributions supported on the set X (throughout, we assume that the o olageerra is implicit). We write
a = b for a. b, & E R if la bl s E. We denote by Ō(.) and Ô(-) the variants of the big-O notation that hide polylogarithmic factors.
Markov Decision Process (MDP) is a tuple M = (S, Q), where S is a measurable state space, A is finite action space, and Q S R - (2 [0, 1J) is the transition- rewarr kernel. We define the transition and reward distributions P S x - (S) and R S x A + MI IJ) as the marginals of Q. By a slight abuse of notation, for any S and A. let P(-ss, and R(-Is, a) denote the distributions P(s, a) and R(s, a), respectively. We further denote by a(s,a)= = So dR (x|s, a) the expected reward for an action E A taken in a state S. Without loss of generality, assume that there designated initial state so S.
Starting from any state s E S, a stationary memoryless policy π : : (3( interacts with the MDP in sequential manner for time-steps r E N. defining probability distribution Pa.s over the episode trajectory (S,, A,, RYN as follows: So = s deterministically, A; ~ T(;)), and (S++1, R,) Q(S;,A)) By slight variation, let P x.x.a denote (for some A) the distribution of the trajectory when Ag a deterministically, while the distribution of the rest of the trajectory is defined analogously.
This allows us to conveniently define the expected state-value and action-value functions in the discounted setting we consider, for some discount factor 0 y < respectively,
1 (s)
Bx.5
Σ rEN
yd R
and (s, Ex.s.a
Σ yd R TEN
for all (s, E -SXA, A, (3)

---

where throughout the paper we use the convention that E. is the expectation operator corresponding to distribution P. (e.g., Ex,, is the expectation with respect to æ..)). It is well known (see, e.g.. Puterman 1994) that there exists an optimal stationary deterministic memoryless policy x² such that and
sup, V (s) V (s)
, (s, a) q" (s.
for all (s, a) E S x A.
Let p" and q² q=" For any policy n, vn and q" are known to satisfy the Bellman equations Puterrann 1994
(P(s'Is,a) a) for all (s x A. (4) ((s)= = Σ x(als)q"(s,a) a) and q (ss,a)) = =r(s,a) + v f (s') + R
x'ES
Finally, we call a policy x deterministic for all states, (s)) is a distribution that assigns unit weight to one action and zero weight to the others. With slight abuse of notation, for deterministic policy π, we denote by (()) the action π chooses (deterministically) in state s E E.S.
3 Confident Approximate Policy Iteration
In this section we introduce CONFIDENT APPROXIMATE POLICY ITERATION (CAPI), our new approximate dynamic programming algorithm. In approximate dynamic programming, the methods designed around oracles that return either approximation to the application of the Bellman optimality operator to a value function ("approximate value iteration"). or an approximation to the value function of some policy ("approximate policy iteration"). Our setting the second. The novelty is that we assume access to the accuracy of the approximation and use this knowledge to modify the policy update, which leads to improved guarantees on the suboptimality of the computed policy.
We present the pseudocodes of API Bertsekas and Tsitsiklis 1996) and CAPI jointly in Algorithm starting from an arbitrary (deterministic) policy To, the algortthm iterates policy estimation (Line and a policy update step (Line 3) times. The policy update for API is greedy with respect to the action-value estimates & and is defined πz(S) = arg max (s, a). We assume that arg max breaks ties in a consistent manner by ordering the actions (using the notation A = (A....... ........AA.. Ala)) and always choosing action R, with the lowest index i that achieves the maximum. For CAPI, the policy update further relies on a global estimation -ccuuorcyccccyyyyyccooo parameter wo, and a set of fixed-states Six S S. For the purposes of this section, is enough keep Six = []. CAPI updates the policy to one that acts greedily with respect to & only on states that are not in Six and where it is confident that this leads to an improvement over the previous policy (Case 5a otherwise, the new policy will return the same action as the previous one (Case (bb. To decide, q(s, (s)) + w is treated as the upper bound on the previous policy's value, and max (s. a) w as the lower bound of the action-value of the greedy action (Eq. 5
arg max a), if Six and q(s, (s)) + w max a ((s,a) w; a
(5a)
Sm. (s) =
(s))
otherwise.
(5b)
Note that St. also depends on w, however, this dependence is omitted from the notation (as is kept fixed throughout).
CAPI can also be seen as a refinmment of CONSERVATIVE POLICY ITERATION (CPI) of Kakade and Langford (2002) with some important differences: While CPI introduces a global parameter to ensure the update stays close to the previous policy, CAPI has no such parameter, and it dynamically decides when to stay close to (more precisely, use) the previous policy, individually for every state, based on whether there is evidence for guaranteed improvement.
Let be any stationary deterministic memoryless policy, 4" S and Six C S. First, we show that as long as 9a is an w-accurate estimate of qr, the CAPI policy update only improves the policy's 's values:
x - R. be any function, w R,,
Lemma 3.1 (No deterioration). Let n' S. Assume that for all E S SSx and a E A.
g"d (*{ N qºt (x,a), a). Then, for any s E S, p (s) 2 (s).
Proof. Fix any S. If s Six or (T and therefore q (s) (s)) Otherwise, s & Six and 9" (s, + i S max (s, w. hence x' r'(s) = arg max (s, a), and it follows by our assumptions that q (5)) 2
+ + 2 max a 4ad (s.a) - w. then x' x's) x(s)
5

---

Algorithm APPROXIMATE POLICY ITERATION (API) and CONFIDENT APPROXIMATE POLICY ITERATION (CAPI)
1: for to do
2: i <- (STIMATE(<;-1)
3: Ti - π
API
CAPI
4: return I
9a (s)) - w= m (s, - (s)))((s)) + + (5, v (s). Therefore, in any case. (s. y* (s). Since this holds for any E S, the Policy Improvement Theorem
Sutton and Barto 2018 Section 4.2] implies that for any s E E, V (s) v (s).
Next introduce approximate optimality criterion for policy set of states: Definition 3.2 (Policy optimality on a set of states), A policy π is A-optimal (for some A 2 0) on of states S' _ S, if for all S', (s) (v) S A.
Definition 3.3 (Next-state optimality on a set of states), A policy x is next-state A-oplimal
(for some A 2 0) on set of states S' S. if for all s S' and all actions a E A, Jres (v* (s') v² (s')
dP(s)) dP(s'|s, A.
Note that in the special case of S' the first property implies the second, that is, if π is A-optimal on S. then it is also next-state A-optimal on S. Next, we show that the suboptimality of policy updated by CAPI evolves as follows (the proof relegated to Appendix A
Lemma 3.4 (Iteration progress). Let x' x Assume that for all E S Spe and a E A, q" (s, a) q" (s. a), and that is next-state A-optimal on S SSix Then x' is (4w y -optimal on Sjx-
3.1 CAPI guarantee with accurate estimation everywhere
To obtain a final suboptimality guarantee for CAPI, first consider the ideal scenario in which we assume that we have mechanism estimate q" (s. a) up to some w accuracy for all and a E A, and for any policy π::
Assumption 3.5. There an oracle called ESTIMATE that accepts policy and returns 9" S x A + R such that for all E S and E A, 9² (s, a) z q" (s,a).
Theorem 3.6 (CAPI performance). Assume CAPI (Algorithm 77 is run with Sjx = O, iteration count to I = [log w/logyl, and suppose that the estimation used in Line 2 satisfies Assumption 3.5 Then the policy πı returned by the algorithm is 5w/ (1 -optimal on S.
Proof. We prove by induction that policy H; is Ay-optimal on S for A 4w EjE(A) Y' + - This holds immediately for the base case of = O, as rewards are bounded in [0. 1] and thus (*() s 1/(1-y) for any Assuming now that the inductive hypothesis holds for - we observe that æ; next-state A-optimal on S = S Six Together with Assumption 3.5 this implies that the conditions
of Lemma 3.4 are satisfied for = æ;-,, which yields v (s) (*(()) 4w + +yAi-1 A,, finishing
the induction. Finally, by the definition of 1, æı is optimmll with A S
4w + y'
S
5w
1-y
1-y
1-y"
Local access planning with -r-realizability
Our planner, CAPI-QPI-PLAN, is based the CONFIDENT MC-LSPI algorithm of Yin et al. 2022 This latter algorithm gradually builds a core set of state-action pairs whose corresponding features are informative. The q-values of the state-action pairs in the core set are estimated using rollouts. The procedure is restarted with an extended core set whenever the algorithm encounters new informative feature. If such new feature is not encountered, the estimation error be controlled, and the estimation extended to all state-action pairs using the least-squares estimator. Finally, the extended estimation is used in Line of API.
CA CAPI-QPI-PILAN improves upon CONFIDENT MC-L.SPI two ways. First, using CAPI instead of API improves the final suboptimality bound by factor of the effective horizon. Second,

---

Algorithm 2 MEASURE
1: Input: state s, action a, deterministic policy æ, set of states S' - S, accuracy e > 0, failure
probability & E [0.
2: Initialize: H < [log(((/4)( -
((w/1) log(2/5)/2)
3: for to n do
4: (S, Rg,0) < SIMULATOR(S.a)
5: for = H do
6: if $ S" then return (discover, S)
7:
A 6 A-x((S)
8:
(5, Ry.h) < SIMULATOR(S, A)
Call to the simulator oracle
9: return (success, 1 Ei=1 En Ri,n)
apply novel analysis on more modular variant of the CONFIDENTROLLOUT subroutine used in CONFIDENT MC-LSPI, which delivers q q-estimation accuracy guarantees with respect to large class of policies simultaneously. This allows for dynamically evolving version of policy iteration, that does not have to restart whenever new informative feature is encountered. Intuitively, this prevents duplication of work.
4.1 Estimation oracle
To obtain an algorithm for planning with local access whose performance degrades gracefully with the uniform approximation error, must weaken Assumption 3.5 This is because under local access, we cannot guarantee to cover all states or hope to obtain accurate q-value estimates for all states. Instead,
interested in accuracy guarantee that holds for g-values only S' S S of states, but holds simultaneously for any policy that agrees with æ on S' but may take arbitrary values elsewhere. For this, we define the extended of policies:
subset
Definition 4.1. Let Iddes be the set of all stationary deterministic memoryless policies, π E Ied.. and S' S. For (π, S'), define II s be the set of policies that agree with E S":
11 {x' Ilaes
(s) x' (s) for all E SS)
We aim to first accurately estimate (s, a) for some specific (s, a) pairs, based on which we extend the estimates to other state-action pairs using least-squares. To this end, we first devise subroutine called MEASURE (Al (Algorithm 2p. MEASURE a modularized variant of the CONFIDENTROLLOO subroutine of Yin al. [2022]. The modularity of our variant is due to the parameter S' that corresponds to the set of states on which the planner is "confident" for CONFIDENT MEASURE unrolls the policy æ starting from (s, for number of episodes, each lasting H steps. and returns with the average measured reward. Throughout, we let [log( (w)g)(()44(111)) - y)) /log y be the effective horizon. At the end of this process, MEASURE returns status success along with the empirical average q-value, where compared to Eq. (3), the discounted summation of rewards is truncated to H. If, however, the algorithm encounters state not in its input S', it returns with status discover, along with that state. This is because in such cases, the algorithm could no longer guarantee an accurate estimation with respect any member of the extended set of policies. The next lemma, proved in Appendix B. shows that MEASURE provides accurate estimates of the action-value functions for members of the extended policy set.
Lemma 4.2. For any input parameters s E S. E A, E I c S.W > 0, E (0, 1), MEASURE either returns with (discover, s') () for some s' $ S' (Line or it returns with (success, q) such that with probability at least 1-t,
gx (x. R q for all x' E
(6)
Suppose we have a list state-action pairs C = (s;, a.)ttec and corresponding q-estimates q (ği)ejcc)- We use the regularized least-squares estimator LSE (Eq, 8 extend the estimates for all state-action pairs, with regularization parameter w22 B (recall that B is defined in Definition I.I
V(C) = AI Eietecnp((sr LSEC.g(s,a) = (y(ss, a), V(C) (aaa (;)
(8)
7

---

For C = q q= O) (the empty sequence), we define LSEc.q(:.)) = 0. This estimator satisfies the guarantee below.
Lemma 4.3. Let be a stationary deterministic memoryless policy. Let C = (Si, ai)ie(n) be sequences of state-uction pairs of some length n E and q q= (qi)ie(n) a sequence of corresponding reals such that for all i E [n]. 9thh (Si,ai) =w qi. Then, for all s,a E S x A,
LSEC (s, a) q=, (s. s g+ [ksp(s, (o(ss,))llv(c)) (V2B+ + (w++)
where & the uniform approximation error from Definition T.1
The proof is given in Appendix C The order of the estimation accuracy bound (Eq. is optimal, as shown by the lower bounds of Du et al. 2019] and Latimmore al. (2020)
We intend to use the LSE estimator given Eq. ( and the bound in Lemma 4.3 only for state-action
pairs where (s, a))lv I (and (d)). We call these state-action pairs covered by C, and
we call a state s covered by C if for all their corresponding actions the pair (s, a) is covered by C:
ActionCover( C)- = ((s.a) S x A : Il (lypss.)llv(cc=== = 1)
(10)
Cover(C) = {s E S Va E A. (s,a) e ActionCover(C)).
(11)
We will use the parameter Six of CAPI (see CAPI's update rule in Eq. 5 to ensure policies are only updated on covered states, where the approximation error is well-controlled by Eq. (
4.2 Main algorithm
Finally, we are ready to introduce CAPI-QPI-PLAN, presented in Algorithm B our algorithm for planning with local access under approximate q realizzabill For this, we define levels
0, 1,...., H, and corresponding suboptimality requirements: For any E [H + 1], let
A = 8(E + w) (Vd+ + +)
Σ JEMI
y-y
13 For each level I, the algorithm maintains a policy лi and a set of covered states on which it can guarantee that πι is Ay-optimal policy. More specifically, this set is Cover( C)), where Cj is a list of state-action pairs with elements Ct = (s), a/) for i E [[G]]. The
for some d = ((d) defined in Eq.
algorithm maintains the following suboptimality guarantee below, which we prove Appendix E after showing some further key properties of the algorithm.
Lemma 4.4. Assuming that Eq. (6) holds whenever MEASURE returns success, Ri is A A1-optimal on Cover(C) C₁) (Definition 3.2 for all I E [H + 1] at the end of every iteration of the main loop of CAPI-QPI-PI.AN
CAPI-QPI-PAA PLAAN aims to improve the policies, while propagating the members of C₁ to C4+1. and so on, all the way to Cи- During this, whenever the algorithm discovers state-action pair with sufficiently "new" feature direction, this pair is appended to the sequence Co corresponding to level O, as there are no suboptimality guarantees yet available for such state. However, such discovery can only happen (d) times. When, eventually, all discovered state-action pairs end up in Cи. the final suboptimality guarantee is reached, and the algorithm returns with the final policy. Note that in the local access setting we consider, the algorithm cannot enumerate the Cover( Cj), but can answer membership queries, that is, for any x E S it encounters, it is able to decide if E Cover(Ci). The algorithm maintains sequences qi, corresponding C,, for each level Whenever a new (s, a) pair is appended to the sequence C₁, corresponding 1 symbol is appended to the sequence qT, to signal that an estimate of q" (s, a) is not yet known.
After initializing Co to cover the initial state so (Lines to 6). the algorithm measures Td (s, a) for the smallest level for which there still exists in the corresponding qr. After successful measurement, there are no more i's left at this level (i.e., in qr), the algorithm executes a policy update on π² (Line 17) using the least-squares estimate obtained from the measurements this level, but only for states in Cover( Cr) (using Six = S \ Cover(Cr)) Next, Line merges this new policy x' with the existing policy Æ/+1 of the next level, setting #e+1 to be the policy x" defined
x" (s)s) (s)..s). if e (over(C(+.)) otherwise.
xs)),
8

---

Algorithm 3 CAPI-QPI-PLAN
1: Input: initial state so E S, dimensionality d. parameter bound B, accuracy w. failure probability
2: Initialize: H =
( for E [H+ + 1]. C = O, qI - 0, .
policy that always returns action AI. w//
3: while True do
> main loop
4: if 3a E A, (so. a) & ActionCover(Co) then
5:
append (50. a) to Co. append 1 to 40 6: break
7:
let be the smallest integer such that qe,m = 1 for some set f HI if no such / exists if // then return ии result) <- MEASURE(S") a. . Cover (dH)) recall Ce.m = (57 a7)) if status discover then
8:
9:
10:
11:
append (result, a) to Cy for some a such that (result, a) & ActionCover(CC) append - to fo
12:
13:
break
qr.m result
15:
if Am' such that Tr.m" = then
16:
< LSEE
17:
x' c- St
Te+1 - (s Te+1 if e Cover(Ce+1) else x' (s)) for a) Cp such that (s, a) É C²-1 do
19:
append (s, a) Cc+1, qe+1
This ensures that the existing policy πe+1 remains unchanged by x" (its replacement) on states that are already covered by Ce+1, and therefore x" &Im ,Cover(Cr..)) = [I .CoverCCr1)) We also observe that Cj can only grow for any I (elements are never removed from these sequences), thus for any update where Cj is assigned new value C (Lines} 11 and 20). V(C)) z V(Ci), and therefore Cover( CP) 2 Cover(C) Cj) and II Coverr(() S I1 Co) Combining these properties yields the following result:
Lemma 4.5. Ifr any E [H), nı and C take some values xt and Colld at any point in the execution of the algorithm, then any later point during the execution, E Coverrr)))C.)) S. II IIeii Cover
Any value in qi that is set anything other than will never change again. Since long as the sample paths generated by MEASURE in Line 9 of CAPI-QPI-PLAN remain in Cover(Ci), their distribution is the same under any policy from 1x,, Coverrv)(C)) the qı estimates are valid for these policies, as well. Combined with Lemma continue hold throughout:
4.5 we get that the accuracy guarantees of Lemma 4.2
Lemma 4.6. Assuming that Eg. (6) holds whenever MEASURE returns success, for any level I and
index m such that 91.m * L. q" (S a(th)) x qi. for all n' (xveCCver(C)) throughout the execution of CAPI-QPI-PLAN.
Once πe+1 updated Line 18 Line 20 we append to the sequence Cest all members of Cr that not yet in Ca+1, while adding corresponding 1 q indicating that these g-values are not yet measured for policy πę+1- Thus, whenever all 1 values disappear from some level [H + 1], by the end of that iteration C/+1 C₁, and hence ActionCover( Ci) ActionCover( (C++1). Together with the fact that for any E [H 1], whenever new state- satteacction pair is appended to Cj, an 1 symbol is appended to qı, have by induction the following result:
Lemma 4.7. Throughout the execution of
Line when E is set, AAciionCove((Ca)
ActionCover Co) ActionCoover(Ci)
As a result, whenever the MEASURE call of Line outputs (discover, s) for some state s, by Lemma 4.2 there is an action a A such that (s. a) & ActionCover(
ActionCoverrCoo) This explains why adding such an (s, a) pair to Co is always possible Line Consider the th time Line 11 executed, and denote s by si and a by aj, and V, AI Σ ( a, a,){p(s T. Observe that as V; V(C), (si, & ActionCover(Coo implies [ly(s;, v > 1. Therefore,

---

E/=1 min (,, ar I1,, i, and thus by the elliptical potential lemma Lattimore and Szepesvári
2020 Lemma 19.4], S 2d log d This incquality is satisfied by the largest value of that 1s, the total number of times MEASURE returns with discover. Since any element of CJ is also an element of Co for any / E [H+ 1]. we have that at any time during the execution of CAPI-QPI-PAN
++ - = ====((
|C|| s 4d log
(13)
When CAPI-QPI-PLAN returns at Line g with the policy ли, it is Ah op-oima on Cover by Lemma 4.4 when the estimates of MEASURE are correct. Furthermore, so E Cover(Co) is guaranteed by Lines to 6 and hence so E Cover(CH) by Lemma 4.7 when the algorithm finishes. Hence, bounding AE using the definition of H immediately gives the following result:
Lemma 4.8. Assuming that Eq. (6) holds whenever MEASURE returns success, the policy π returned by CAPI-QPI-PLAN A-optimal on {5o} for
A 9 (w) =
To finish the proof of Theorem 1.2.
we only need to analyze the query complexity and the failure probability (i.e.. the probability of Eq. (6) not being satisfied for some MEASURE call that returns success) of CAPI-QPI-PLAN:
Proof of Theorem 1.2] Both the total failure probability and query complexity of CAPI- HAPI-QPI-PLAN depend on the number of times MEASURE is executed, as this is the only source of randomness and of interaction with the simulator. MEASURE can return discover at most |Col times, which is bounded by d by Eq. (13 For every / E [H], MEASURE is executed exactly once with returning success for each element of Cj. Hence, by Eq. (13) again, MEASURE returns success at most dH times, each satisfying Eq. (6) with probability at least 1 - 1 5/(HH) by Lemma 4.2 By the union bound, MEASURE returns success in all occasions with probability at least 1- 5. Hence Eq. (6) holds with probability at least 1 - 6, which, combined with Lemma 4.8 proves Eq. ①
Each successful run of MEASURE executes at most nH queries (n is set in Line 2 of Algorithm 2
Since H (1 y)- 1og(4w-11g -)- Ō((1 -))-- in total CAPI-QPI-PIAAN executes
most Ô (d(1 - ?) queries. As this happens most dH times, obtain the desired bound on the query complexity.
Conclusions and future work
In this paper we presented CONFIDENT APPROXIMATE POLICY ITERATION, a confident version of API, which can obtain stationary policy with a suboptimality guarantee that scales linearly with the effective horizon H ((/(( -))). This scaling is optimal shown by Scherrer and Lesner [2012]
CAPI can be applied to local planning with approximate g -'-rralizabiility (yielding the CAPI-QP -PI- PLAN algorithm) to obtain sequence of policies with successively refined accuracies cally evolving set of states, resulting in a final, recursively defined policy achieving simultaneously the optimal suboptimality guarantee and best query cost available in the literature. More precisely, CAPI-QPI-PLL achieves Ō(EVdH) suboptimality, where is the uniform policy value-function approximation error. We showed that this bound is the best (up to polylogarithmic factors) that is achievable by any planner with polynomial query cost. We also proved that the Ô (dH'' query cost of CAPI-QPI-PLAY is optimal up to polylogarithmic factors in all parameters except for H;; whether the dependence on is optimal remains an open question.
dynami-
Finally, our method comes at a memory and computational cost overhead, both for the final policy and the planner. is an interesting question if this overhead necessarily comes with the API-style method we use (as it is also present in the works of Scherrer and Lesner 2012 [cheererr] 2014), or if is possible to reduce by, for example, compressing the final policy into one that is greedy with respect to some action-value function realized with the features.
10

---

Acknowledgements
The authors would like thank Tor Lattimore and Qinghua Liu for helpful discussions. Csaba Szepesvári gratefully acknowledges the funding from Natural Sciences and Engineering Research Council (NSERC) of Canada, "Design.R al-assiteed CPS Design" (DARPA) project and the Canada CIFAR AI Chairs Program for Amii.
References
Dimitri P. Bertsekas. Dynamic Programming and Optimal Control: Approximate dynamic program-
ming, volume II. 4 edition, 2012.
Dimitri P. Bertsekas and John N. Tsitsiklis. Neuro-Dynamic Programming. Athena Scientific, 1996.
Simon S Du, Sham M Kakade, Ruosong Wang, and Lin F Yang. Is good representation sufficient for sample efficient reinforcement learning? In International Conference on Learning Representations, 2019.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137-2143. PMLR, 2020.
Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In In Proc. 19th International Conference on Machine Learning. Citeseer, 2002.
T. Lattimore and Cs. Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.
Tor Lattimore, Csaba Szepesvári, and Gellért Weisz. Learning with good feature representations in bandits and in RL with generative model. In JCML, pages 9464-9472, 2020.
A Woodbury Max. Inverting modified matrices. In Memorandum Rept. 42, Statistical Research Group, page 4. Princeton Univ., 1950.
Remi Munos. Error bounds for approximate policy iteration. In ICML, pages 560-567, 2003.
Remi Munos. Error bounds for approximate value iteration. In AAAI, pages 1006-1011, 2005.
Martin L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley-Interscience, 1994.
Walter Rudin et al. Principles of mathematical analysis, volume 3. McGraw-hill New York, 1976.
Daniel Russo. Approximation benefits of policy gradient methods with aggregated states. arXiv
preprint arXiv:2007.11684 2020.
Bruno Scherrer. Approximate policy iteration schemes: a comparison. International Conference Machine Learning, pages 1314-1322. PMLR, 2014.
Bruno Scherrer and Boris Lesner. On the use of non-stationary policies for stationary infinite-horizon Markov decision processes. F. Pereira, C.J. Burges, I.. Bottou, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 25, 2012.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Andrew Wagenmaker, Yifang Chen, Max Simchowitz, Simon S Du, and Kevin Jamieson. Reward- free RL no harder than reward-aware RL in linear Markov decision processes. arXiv preprint arXiv:2201. 12006 2022.
Yuanhao Wang, Ruosong Wang, and Sham Kakade. An exponential lower bound for linearly realizable MDP with constant suboptimality gap. Advances in Neural Information Processing Systems, 34, 2021.
Gellért Weisz, Philip Amortila, and Csaba Szepesvári. Exponential lower bounds for planning in MDPs with linearly-relizzable optimal action-value functions. ALT, volume 132 of Proceedings of Machine Learning Research, pages 1237-1264, 2021.

---

Chenjun Xiao, Ilbin Lee, Bo Dai, Dale Schuurmans, and Csaba Szepesvari. The curse of passive data collection in batch reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pages 8433-8438, 2022.
Dong Yin, Botao Hao, Yasin Yadkor, Nevena Lazié, and Csaba Szepesvári. Efficient local planning with linear function approximation. International Conference on Algorithmic Learning Theory, pages 1165-1192. PMLR. 2022.
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Learning near optimal policies with low inherent Bellman error. In International Conference on Machine Learning, pages 10978-10989. PMLR, 2020.
Dongruo Zhou, Jiafan He, and Quanquan Gu. Provably efficient reinforcement learning for discounted MDPs with feature mapping. arXiv preprint arXi:: 13/65, 2020.
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? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits. hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're rou're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or 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, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "pLbYbcMqrw", "reviewer": "Reviewer_2pLv", "summary": "This paper proposed a new algorithm in the setting of MDP with approximate linear value function (for any policy, the value function is approximately linear in l infinity norm with respect to a given feature map) along with a local access simulator. The algorithm CAPI achieves the best known sub-optimality bound along with the best known query cost in the local access setting, previous algorithms achieve only one of them. The algorithm is based on Policy iteration and a new technique of partition the observed state space into layers and planning policies for each layer with a refined accuracies, which maybe of independent interest.", "questions": "(1) Is there a lower bound in the random access setting, how does the result compare to it?\n\n(2) Is it possible to use this idea in the general function approximation setting? \n\n(3) What can we do if we are not granted with the feature but only have a feature class?", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: The algorithm is highly novel although the key idea of core set is proposed in previous papers. The proof is clean and looks sound to me. The result is pretty great since the algorithm achieve both the best known query complexity and accuracy. (Compared to [Lattimoore et al., 2020] and [Yin et al., 2022])\n\nWeaknesses: Lack a lower bound. A more detailed discussion of why previous algorithm [Yin et al., 2022] cannot achieve the tight bound is recommended. As well as a comparison of computation complexity with previous methods.", "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": "lsim9qy4PC2", "reviewer": "Reviewer_UY7n", "summary": "The paper presents a confidence approximate policy iteration algorithm for discounted MDPs. The authors then prove that the algorithm produces a deterministic stationary policy with an optimal error bound which scales linearly with product of the effective horizon and the worst-case approximation error of the action-value functions of stationary policies.", "questions": "Algorithm and proof techniques very similar to existing works, the contribution is not very clear", "limitations": "Proof techniques very similar to existing works", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The authors extend previous works to improve on the performance bounds but it is very similar to previous works by Yin et. al.", "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": ["Responsible Research Practice (e.g., IRB, documentation, research ethics)"]}, "extra_text": {}}, {"review_id": "X8_7cuI1bAT", "reviewer": "Reviewer_eM8M", "summary": "The authors consider the linear action value function setting, and in particular the local planning problem with value-based methods.\nThey obtained an algorithm whose approximation error grows linearly with the horizon all the while returning a stationary policy. In terms of query complexity, they achieve the best known accuracy and query complexity at the same time.", "questions": "See above", "limitations": "The work is quite technical and theoretical and could be of interesting to a more narrow audience. Since the work seems to be computationally implementable, it would be nice to have some limited experiments as well (in simulated domains), although this is not standard for this sub-area of RL ", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I believe that this is not the first result with an approximation error that scales linearly with the horizon. For example, see what could be inferred from “Q* Approximation Schemes for Batch Reinforcement Learning: A Theoretical Comparison” by Xi et al. (To be clear this work is quite different to the proposal here and does not diminish the novelty of the work submitted).\n\nI believe that although the work strictly improve on prior art, it is nonetheless quite technical and of potential interest to a technical audience.\n\nQuestion: this work revolves around improving the dependence on the approximation error. However, the definition of approximation error seems is very strong (\\ell-infty). In practice, such value is likely to be large. Given that a local access is assumed, can it be relaxed to other more forgiving definitions? In particular, I am referring to non \\ell-\\infty definitions.", "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