Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning
Authors: Zihan Zhang
Yuhang Jiang
Yuan Zhou
Xiangyang Ji
Venue: NeurIPS 2022 Accept (2022)

Abstract: 	In this paper, we study the episodic reinforcement learning (RL) problem modeled by finite-horizon Markov Decision Processes (MDPs) with constraint on the number of batches. The multi-batch reinforcement learning framework, where the agent is required to provide a time schedule to update policy before everything, which is particularly suitable for the scenarios where the agent suffers extensively from changing the policy adaptively. Given a finite-horizon MDP with $S$ states, $A$ actions and planning horizon $H$, we design a computational efficient algorithm to achieve near-optimal regret of $\tilde{O}(\sqrt{SAH^3K\ln(1/\delta)})$\footnote{$\tilde{O}(\cdot)$ hides logarithmic terms of $(S,A,H,K)$} in $K$ episodes using $O\left(H+\log_2\log_2(K) \right)$ batches with confidence parameter $\delta$. 
	To our best of knowledge, it is the first $\tilde{O}(\sqrt{SAH^3K})$ regret bound with $O(H+\log_2\log_2(K))$ batch complexity. Meanwhile, we show that to achieve $\tilde{O}(\mathrm{poly}(S,A,H)\sqrt{K})$ regret, the number of batches is at least $\Omega\left(H/\log_A(K)+ \log_2\log_2(K) \right)$, which matches our upper bound up to logarithmic terms.
	Our technical contribution are two-fold: 1) a near-optimal design scheme to explore over the unlearned states; 2) an computational efficient algorithm to explore certain directions with an approximated transition model.ion model.

Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning
Zihan Zhang
Yuhang Jiang
Yuan Zhou
Xiangyang Ji
Abstract
In this paper, study the episodic reinforcement learning (RL) problem mod- eled by finite-horizon Markov Decision Processes (MDPs) with constraint on the number of batches. The multi-batch reinforcement learning framework, where the agent is required to provide a time schedule to update policy before everything, which particularly suitable for the scenarios where the agent suffers extensively from changing the policy adaptively. Given a shritehhorzoon MDP with S states, actions and planning horizon H, we design computational efficient algorithm achieve near-optimal regret of Ö(V AH' In(1 (n(1/5) in K episodes using O (H + log, loga( K)) batches with confidence parameter 8. To our best of knowl- edge, it is the first S(H33 regret bound with O(H logz log2 (K)) batch complexity. Meanwhile, the number of batches is at least (H/ log ( (K) + loga log, ()), which matches upper bound up logarithmic terms.
show that achieve (poly A, H)VK) K) regret,
Our technical contribution are two-fold: a near-optimal design scheme explore over the unlearned states; 2) an computational efficient algorithm to explore certain directions with an approximated transition model.
Introduction
In reinforcement learning (RL), the learning agent interacts with the environment to maximize the total reward by making sequential decisions. The agent typically has to achieve two seemingly very different goals: to try as many actions and reach as many states as possible so as to learn more information about the environment (a.k.a. exploration) and to follow the policy that collects the high rewards according to the learned information (a.k.a. exploitation). To address this exploration- exploitation dilemma and achieve the near-optimal regret bounds, the agent usually needs adjust his/her strategies adaptively based on the historical trajectories and make frequent policy changes Azar al. 2017 Zanette and Brunskill 2019 Zhang al. 2020].
On the other hand, however, too much adaptivity requirement usually leads to lower level of paral- lelism, impeding the large-scale deployment of the RL algorithms (which is often in distributed manner). Frequent policy updates also suffer the cost of re-deploying policies many practical applications. For example, in medical domains, it often requires complete discussion among many experts to change the treatment plans, which is not affordable in terms of both time and monetary cost [Lei et al. 2012, Almirall al. 2012 2014): in RL for hardware placement [Mirhoseini et al.) 2017 rewriting the program into the hardware for too many times is strongly discouraged. Similar
http///mmmmsssssnuaaaaaaaaaa wwi.gghhaaeeuu....m edu. cn 1 Department of Automation, Tsinghua University, jiangyh19@mail
Department of Automation. Tsinghua University, Samagghhhemmiiss.ttintuuu tainghua.
Yau Mathematical Sciences Center & Department of Mathematical Sciences, Tsinghua University,
yuan - www.utsinguuu.eeeeeeeeooo en
Department Automation, Tsinghua University, xyji@tsinghua.co edu.
(.)) hides logarithmic terms of (S, A, H.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

challenges also arise in applying RL to personalized recommendation system Yu et al., 2019 and database optimization [Krishnan et 2018
In such cases, the learning agent should minimize the number of policy switches while keeping the regret affordable. [Bai et al. (2019) first proposed the provably efficient RL. algorithms with low switching costs under the Ql-earning algorithmic framework together with the lazy update techniques. However, their method needs to actively monitor the data in real time determine whether a policy change is to be initiated. In other words, although the number of policy switches by [Bai et al. 2019 low, the (usually long) time periods when the same policy is used still cannot be parallelized due to the policy-change trigger in their algorithms which is intrinsically sequential.
In order to address this problem, we propose and study under the framework of multi-batch RL, where the learning agent has to determine the number of batches and length of each batch before the learning process starts @ and uses few batches possible to achieve low regret. Multi-batch RL algorithms can be easily deployed in a distributed fashion as the episodes during the same hatch can be easily and fully parallelized. The idea of batch learning is also being widely practiced. For example, in medical trials, the medical center usually collects the data during a fixed time period among a batch of patients and then designs the experiment for the next phase based the learned information in previous phases [Li et al. 2012 Almirall et al. 2012 2014
Formally, define mulli-batche RL and batch complexity as below.
Definition (Multi-Bate RL with complexity M). The agent determines a group of lengths [tm - such that ΣM= fm K before the learning process starts. For m = 1.2...... M, the agent sets a policy xt and then follows T. for tm episodes.
We highlight that an upper bound for batch complexity implies the same upper bound for global switching cost, since each policy switch means new batch. It is also worth noting that the proposed batch RI. framework is fully parallelizable during each batch for the applications where dataset comes in batch (e.g., clinical trial). Like other RL. settings, have the natural and interesting question: Question 1. Is it possible to achieve near optimal batch complexity, while keeping the regret O(VSAH&K).
We provide positive answer for Question which we state as below. Theorem Le L = In(2/8). For any episodic MDP, with probability 8, under Algorithm the regret in T episodes is bounded by
(T) & ò (VSAHI*K> + S A 22
+ * S
and the batch complexity is bounded by O(H + log, log, (K)). Moreover, the computational cost of Algorithm 7 Ö(S* AH + 5 A H2
On the other hand, we show a lower bound of batch complexity as below.
Theorem 2. For any algorithm with (p A, H) K)) regret bound, the batch complexity is at least (H log (K) + log2 loga (K)).
Compared to the lower bound of 22log log, (K)) in Gaa et al., 2019 for multi-armed bandit problem, additional /2H// logg((K) batches are required explore the structure of the MDP.
Due to space limitation, we defer the full proofs of Theorem T and Theorem to Appendix and Appendix(B Brespecctivel
Our contribution. We propose the framework of multi- batch RL, and first achieve O(H + logg (og)(K)) sample complexity bound with the near-optimal O(VSAH3)) regret bound with an efficient algorithm. We also prove that for any algorithm with ((poly(S,))))) A, A, H) regret, the global switching cost is at least Q log (K) + log, log.2 (og),K)), which implies nearly matching lower bound of Q log, ()) + log, log, (K)) for the batch complexity. We also note that the O(H log, log,(K)) batch complexity implies O(H + log, log)(K)) bound for the global switching cost, which is also a near optimal upper bound.
'In contrast, Bai et al. 2019 can update the policy at any time.
Throughout the paper to denote (2/66).

---

2 Related Works
Bandit algorithms with limited adaptivity. Bandit problem with low switching cost is widely
studied in past decades |Cesa-Bianchi et al.; 2013 Perchet et al. 2016 Gao et al. 2019 Simehi
Levi and Xu 2019 Desa-Bianchi et [0113 showed an ( regret bound under adaptive
adversaries and bounded memories, Perchet et al. [2016] proved regret bound of ((( ar for the two-armed bandit problem within A/ batches, and later Gao et al. [209]] extended their result to the general A-armed case. Besides the setting of classical multi-armed bandit problem, other settings has also been studied, e.g., multinomial bandit problem [Dong et al. 2020) and linear bandit problem
[Ruan al. 2020
Episodic reinforcement learning with low switching cost. For model-based algorithms, by doubling updates, the global switching cost is O(SAH (og [og)
while keeping the regret O(vSAK Azar et al. (2017). For model-free algorithms, Bai et al. [211 first studied RL with
low switching cost. They proposed Q-learning algorithm with lazy update to achieve Ó S SAK H4) regret bound and O(SAH* log(K/AA) (/A)) local switching cost. Recently Zhang et al. [2020] estab-
log( K/A)) local switching cost. Be- sides, Gao al. [2021] generalized the problem Linear RL., and established regret bound of o(vd ()* with O(dH log(K)) global switching cost. Recent work Qiao al. [2022) achieved
lished a better regret bound of Ó(VSA( H3) and
O(HSA log, (K)) switching cost and O(poly(S, A, H))))) regret with a computational inef-
ficient algorithm.
Regret minimization for reinforcement learning.
There is long line of works devoting to regret
minimization for RL problem [Kakade| 22033 Jaksch al. [001 Bartlett and Tewari [2099] Dann
et al. 2019 Azar et al.
2017 Jin et al.] [2018] Zanette and Brunskill 2019 Zhang and Jil 2019] Zhang
et al. 2020 Li et al. 2020, Zhang et al.] 2021]. For tabular setting, near optimal regret bound of
O(v S AT has been established by [Azar al. 2017 Zanette and Brunskill 2019 Zhang et al.
2020 for both model-based and model-free algorithms. However, fewer algorithms focused on the
setting of multi-batch RL.
3 Preliminaries
Episodic reinforcement learning. M (S,A,r,,,s1) where S x A is the discrete state-action space, r =
is the knowr reward function, P (P, (s))sxxxx is the unknown transition model and 81 is the fixed initial state We assume that the reward function Tn (s, a) E [o, 1] for any (h, 8, a). In each episode, the agent starts 81, then takes actions and transits to the next state step by step, and finally conducts the trajec- tory ((hh, an, 81+1)) The target of the agent is to maximize the accumulative reward function > E
A policy π can be viewed as a series of mappings { where S - A maps to distribution over the action space the h-th step, where Fi (a|s) is the probability taking action at state s of the h-th horizon.
Given policy the (optimal) Q-function and value function are given by
H
(% a) = Ex
Σ
rh (sw,, and (sn) an) = (s, a)
28 a) sup (T rell
H
(sKc, ax) (wr)/a
VI ViT (8) = En
V max (s,
'This is common assumption since the uncertainty of reward function dominated by that of the transition model.
'The more general case, where the agent starts from fixed initial distribution, could be reduced to our setting by increasing H by
3

---

Let x denote the policy in the k-th episode. Then the regret is given by
RK) =- Σ (v) V/ (81)).
Notations In this paper, we use Ex,pl (IP (P...pl))) denote the expectation (probability) following policy under transition model p. In particular, [=I-)(( denotes the expectation (probability) following under the true transition model P. We define the general value function
H
("' (p) Ex.p
Σ
r (sh. an)
We use 1 to denote the S-dimensional vector [1, 11.1.... ..... 1TT and In.s. to denote the reward func- tion r' such that (8', aa) = [[ 8, 8, = (K', SM, a')] We also define {dī (s, a)) be the occupancy distribution of That is, (s = E,[I[(s,, an) (s, a)ll- A is used to denote with the same dimension, we write x' y as ry for
the d-dimensional simplex. For two vector convenience. For e A and v IRS, we define V(p, u) = po? (pu)?. For N > we use [N] to denote the set [1, ...,, NJ.
4 Technique Overview
In this section, we first introduce the policy climination framework, which enjoys the near-optimal batch complexity. Then summarize the technical challenges achieve the near-optimal regret bound efficiently under this framework. At last, we introduce our major technical contributions.
4.1 Policy Elimination Framework
Following the methods in multi-batch bandit learning Perchet et al. [2016). Gao et al. [2019), construct our main algorithm using policy climination. Like most model- based reinforcement learning methods, maintain confidence region P for the transition model, where the true transition model Pe P with high probability. Before each batch starts, for policy и and a reward function u, by extended value iteration (See Algorithm in Appendix C.2, we able to compute the confidence interval [L (u, P), (u, P)] for the value function of π, where
UT P) max W" 12,1/;;
I ("" == min W (v, w/EP
P'EP
Here is a virtual state for the infrequent cette-action-se triples (See Function clip in Algorithm 2 The reason why we give reward 1 for z in computing the upper confidence bound to encourage exploration to these infrequent state-action sate-actionnstate triples.
By policy elimination we get II(r, P) = at U (r. (r,P) > sup..LL P)] as the set of survived
policies. The next step to choose policy π E [1(r, P) and execute π in the current batch. Defining pm to be the confidence region for the transition model after the m-th batch and gap"+11 max (U=",, pm) L"(r, (r, pmm), p)"), the regret the m + 1-th batch could be bounded by pm+1 pm+1gapp gggam."* m+1 Therefore, the main task is to design efficient exploration policy to reduce gap" for each 1 & & M.
4.2 Technical Challenges
Following the policy elimination framework above, we have two major challenges to achieve the near-optinal regret bound with an efficient algorithm.
Difficulty exploration Fix the reward function and confidence region P. To construct tight confidence interval for every policy
[r) need find policy π E II(r, P) to collect enough samples for each (h, s, a). To address the problem, Qiao et al. [2022 proposed an algorithm named APEVE, which learns each (h, s, a) triple independently. More precisely, for each (h, s, a) [H] x S x A, the algorithm searches for policy nt h.s.4 to maximize the probability of visiting (h, s, a)

---

over [I(,, P). and then execute Th,*,0 to collect samples for (h, 8, a). However, this algorithm might triples may match along with the same exploration policy. As shown in Qiao et al. 2022 the regret bound might be sub-optimal with this algorithm. Therefore, to achieve the near-optimal regret bound, we need design new exploration strategy to utilize the correlationship among different horizon-state-actio triples.
be inefficient in sampling, since different
Difficulty in efficient implementation Because the policy set [I. P) might have exponential size, naive enumeration is not applicable to searching for good exploration policy. As a consequence, it requires additional efforts to study the structure [T, P). For example, when = 0, [T(r. P) the set of all possible policies. In this case, we can use extended value iteration (See Algorithm 5 to find the policy which visits (h, 8, a) most frequently.
4.3 Key Techniques
Near-optimal design scheme Unlike RL algorithm with limited switching cost, in multi-batch reinforcement learning, the agent can not change the policy adaptively. As result, we need to design a policy with proper coverage ratio for all the survived policies. That is, using the data collected following this policy, the length of the confidence interval for any survived policy is bounded by uniform threshold.
Recall that (s, a) E, (sh, a.)) = (s, a)]- Using classical regret analysis for tabular RL Azar et al.] 2013] Zanette and Brunskill 2019), for a fixed policy æ, the length of confidence interval for π could be roughly bounded by
Varn(s, a) an(
dT Σ 8,a.h
Σ (h s...h
Σ a,0
aa)n
Cauchy's s ineq.
an(s,a)
where (ara(s, a) is the variance term with respect to Ph.s.a and V *b41 (+), and Na(s, > 1 is the count of (h, 8, a).
Because Ee,,,h (s, Var,,,,, a) could be uniformly bounded by O(H?) using classical analysis, di (3,a).)
we focus on bounding the term Es,a, N,(a,a) Suppose the policy for current batch म. After this batch, we roughly have that (s, a) od (s, a). So it corresponds find policy म II(r, P) to (s,(),)) For this problem, we have minimize the worst-case coverage number max,nel(r:P) Σn, di(ssa)
the lemma below, and the proof is deferred to Appendix E.T
Lemma 1. Let d > be an integer. Let X (A such that
Then there exists distribution D over X,
dm I;
max
md,
dm
V1
where y = (ym)dm can find an approximation solution for D in poly([?X() time.
1dm = Ez-D[x.. Moreover, if has a boundary set OX with finite cardinality, we
Plugging X (d))
((), d SA and H into Lemma there exists policy स being a mixture of policies in 11(r, P), such that maxrel(r,P)) Es,
SAH. In this way, we can find the desired exploration policy स by assuming the knowledge of (d] )) for all x E II(, P).
(3.0)
(s.a)
Given the design scheme above, it remains two problems, for which we present solutions below: 1) (d) h-1 is unknown; even assuming (dd((..)))) known, is hard to find स since the cardinality of (d)(( e (TrrP)) might be exponential in SH.
h-1 we consider to construct a tight confidence region for the transition model to estimate the occupancy distribution up to a constant ratio.
Constructing tight confidence region To estimate [d] (,, H
5

---

Definition 2. We say confidence transition region P &h, Pho is tight with respect to pf iff (i)p' P; (i) H Ph,,,,,s' & Ph, & e Ph.,,,, for any (h, 8, a 8') and any ph, Ph,s,ai (iit) Ph,e.a has the form Ph,e, = {p A a p b,, i 1.2,..., m] where m & PM
In model-based reinforcement learning, these conditions are natural and is easy to construct a tight confidence region with acceptable error.
Once we have confidence region which is tight w.r.t. the true transition model P, for any policy and (h, 8, a), we can estimate the expected visit count W"1,, by W (1n,,,, p) for any e P because
WT (h,,,a (T di (8, & eW (IT,(,,,,.
With W (I,,.,;:)) p) as approximation of (s, a), we can continue the analysis above by paying constant factor.
To learn such confidence region, by Bennet's inequality (Lemma 3), it suffices visit (h, s' To for C1 H2, for each (h, s, a, s'), where C1 is an universal constant. By this idea, we try to visit each (h, 8, a, 8') ) as much possible. In the meantime, it is very possible that some (h, 8, a, s') tuples extremely hard to visit. Fortunately, with proper exploration scheme, we can show that the maximal probability to visit such tuples is well-bounded, that these tuples could be ignored by suffering regret O(vT).
Computational efficient design scheme Assume the confidence region P is tight w.r.t. P. We invoke reward-zero exploration to lear a sub-optimal solution for the problem min=etl(rPP)) maX+ell(rP)) En,,, (s,a) Let E P be fixed and define (s, a) = W [1,(1,,,
(s.aa)
be the approximation for di, (s, a). We define म' = arg maxxell(yPP) (*'r', for 1 < i k K
where (8, a) min have that
Let म be the mixture of (5t (#t For any policy we J.
Σ de' (1.a)
dh a) min {
Σ dh (s.a) a) min 8,
(s k
Σ
(4)
s,ah
(r' pp)
(5)
W (r".)) (p)
(6)
k
E di (s. 1
Σ
di (s, a) min
5,ah
max oi (s, max -i 15 (8, (0,a),1)
Σ log
& (ogH
Here
4 holds by the tightness of P. ( holds by the fact that (s,ss)) r (s,
min { (3)), k) for any (h, a), and 66 holds by the optimality
min
2m d (s,a)
of # for 1 I k. With in hand, max P) En (s.a) is roughly bounded by d.
[T] which nearly matches the best worst-case coverage number number of SAH. O log(K))
10 A tuple (h, a, s') is visited means (sh. 8841) = (s, s'). "W remark the there is still gap between max Er,
(f di [c.a] and Enan di (s.a)
min [(.o K²). Actually 7 is sufficient for further regret analysis.

---

Algorithm Main Algorithm
1: Input: state-action space S x A, number of episodes K, confidence parameter d;
2: Initialize:
(2 11 144 k2 2885 A HHH'VKK
3: (Di) - Raw Exploration(0, Ø, k1);
4: (D2) + Raw Exploration(r, D k2)
5: Policy Elimination(D2, Hk1 Hk2).
Computational efficient constrained exploration Let u, u' be two reward functions and P be set of transition models. As stated before, for general [[u,, P) it might be non-trivial to solve the problem के = arg maxxelllu,P W W" .p) for fixed p P. As a trade-off, we turn find some policy á IT( P) such that W (u', .)) 3 cmaxxeel(a.)) W"''', (f'(u)),, where c > O is some universal constant. The problem turns out to be a RL problem with a soft constraint. For general [I, [u, P), the problem might be hard to solve. Fortunately, the benefit of the tight property of P, we can find such गł efficiently.
5 Algorithms
In this section we present our algorithms. The main algorithm (Algorithm consists of three stages.
In the first stages, conduct naive exploration identify the tuples which are hard visit, which we called infrequent tuples. In particular, the length of the second stage is slightly larger than that of the first stage, where In this way, we can bound the regret in the first stages by Ö(VSAH while the probability of visiting the infrequent tuples is small enough.
the dataset in the first stage reduce the regret in the second stage.
After ignoring the infrequent tuples, could obtain tight confidence region. Given the right confidence region, we compute the confidence region for each policy and conduct policy climination in the third stage. The first and second stages contains O(H) batches, and the third stage contains Olog, logg K)) batches. So the batch complexity of Algorithm [ is O(H + log, log, (K)). Below describe Raw Exploration (Algorithm ( and Policy Elimination (Algorithm) 3 in detail.
5.1 Raw Exploration
Given a dataset D with counts (Na(s, a, 8')}, we define the set of known tuples as (1,,,,,,)) (a,s, a, 8') > Cj H22) and the left tuples are regarded as infrequent tuples.
In Algorithm 2 we are given a dataset. Then we compute the corresponding confidence region P in Line 20 where an, n²)
An's
We conduct exploration layer by layer over policies in the set of survived policies [[(;; P). By visiting each (h, 8, a.) as much as possible, we can judge whether a tuple (h, 8, a',") 3') is hard to visit using policies in PP)
Given the set of known tuples W, we redirect all tuples not in W to an additional absorbed state using clip(:.-). Once prove that the probability of reaching is small enough for the any optimal policy, we can directly learn under the clipped transition model.
In Line 6 Algorithm 2, the algorithm Policy Search is invoked. Given any reward u, u', any confidence region P and threshold > 0. this algorithm returns policy II(,, such that (" p) 2 cmaa ( p) - with some universal constant e > O. Moreover, when P is tight w.r.t. the true transition model P after clipping, the time complexity of the algorithm Oppoly log(1/c)). The algorithm and corresponding analysis is postponed to Appendix
1 can not be regarded as also worth noting that executing each Th.s... with probability 34 (history-independent)) policy because the agent need to keep in mind which policy is chosen in current episode. In contrast, the agent only needs to observe current state take actions following policy. To address this problem, we define an operator Sum to take sum over policies under some transition model. Formally, we have the lemma below and postpone the proof Appendix E.2
7

---

Algorithm 2 Raw Exploration(u, D,
Input: reward function u. dataset D, length k;
2: Initialize: C₁ 200:
3: for 1,2, ..,, H do
4: P - CR(D);
5: for (s, a) E x A
6:
hh, Policy Search(u, In, P);
7:
end for
8:
p - arbitrary element in P:
(* pp) Sum (1 1. R P) (h.s.a)
9:
Thhh be the policy which is the same 5 in the first 1 steps, and be the uniformly random
policy in the left / - + steps;
Execute x² for k episodes, and collect the samples Dr:
12: + DUDD Du:
end for
14: return: (D):
15: Function: CR(D):
a, 5') - count of (h, 8, a, 8') in D, for (s, (s,; (s,
17: Na(8,a) - max EE3 (a(s, 8 for all (s,a);
Phaaass - Nula.a.9) ((,,8,,,8);
18:
Na(a.a)
19:
W 8,,,8))))) Nu(s,a,8)) C.H:):
1 20: PhIna {p A Ip ph.s & (NN,(s, N'), eS). 8(h,
21:
Ph.ca - (clip(p, W)
hh v(h,8,0) Return: @h. Ph.e.a
23:
Function: clip(p, W)
24:
Phisa,s - ph.s,a,''s V(h,,,,,st W; W;
25:
Phona.ss' < 0, (,,,,,,,, a.))'))))) W:
26:
Ph.a.a. L ,'W Phaa,,, s,,, S
27:
Ph,2. 1,, ah, [H] x A;
28:
Return: p.
Lemma 2. Let ((h. () Ph,s,a
be a set of transition models such that Ph.s.a = A convex for any (h, 8, s,)). Let {( P')), | be sequence of
pairs such that p e P. For any (dii such that X₂ > for 1 and E, X 1, there exists policy a and P P, satissfyin that
W (In,,, P) Edew'' Pi
(8)
for any (h, 8, a) E [H] S x A. Farthermore, the time complexity find {,,, P) could be bounded by O(nS3 H2H
Therefore, for any ()i, n², pT) satisfying En d and X; > for i > as input, there exists {T,, P} such that WT1,, P) = E, AW= (1, Pi) and Ph.s.a Convex({ (Pr h )r=)) for any (h, 8, a) [H] S A, where Convex((1) denotes the convex hull of the set 4.. Then Sum defined as Sum( (Ax π² pije ) = P).
5.2 Policy Elimination
Given the dataset collected in the first two stages, we first compute the known set W. Unlike Algorithm 2 we do update W in the rest time because the first stages can ensure that the probability of visiting WVC is O(Iv/K).
As mentioned in Section 4 for each batch, we invoke reward-zero exploration to search for the policy with near-optimal coverage. Based such policy, provide uniform bound for the length

---

Algorithm 3 Policy Elimination
1: Input: dataset D, length k;
2: Initialize: D - D, P - (A5) C - 100, 1/2 (s) - h + 1, v(h, 8) [ x S:
M Km K1--t for m = 1.2....,M. [log2 2og2(K)); (K)};
3: [s 0, 5') - count (h, 5, in D:
4: W < {(h, 8, a,), (N,
C,ff'
5: for m = 0, 0..,,.....
do
6: pm pm-1_pppp- CR* Dm D W. ( (s))
7:
π m++ ( (P");
8:
if mm'-1 Km < k then
9:
Execute n. m++ for Km- episodes;
else
11:
Execute n m+1 for ( m m1=1 Kmy) episodes;
end if
13:
D m++
the dataset in the (m + 1)-th batch;
14: Update the dataset Dm+11 < Dm U D m+
oh (s) maxx ET.. En'=h Th (Sh, an) for (h₂,) E [M] S;
16:
end for
17: Function: CR D' W. v):
18:
(Ni(s, a, s counts in D, (N, max Nu,s, s)), for all (h, 8, a, s'):
Ph.s.as N,la,a,d))
Na(ma) v(h,s,
20: (Nu(s, a, s')} counts in D', ()) max Nn,s,,, 13 for all sh,
Nu(s,a,d) s,h,,, Pha Na(o,)
21:
22:
PhIna- p 1 Ph.s.vl & a Nd..a)))
Ip- )h < a (N((Nss ph.., 3) v(h, s.a);
23: Ph.sa (clip(p, W) : e Ph,na), 8,h,;
24: Return: &h,s,a Ph.xa.
25: Function: Design(P):
p- a-rbitrrary element in P: 27: for = 1,2,... 3 do
28:
d (s. w (1 p) for < $ E ii- and any s,));
29:
()) - -min-
s(h,s.a);
8. (s.a) 30: #' Policy Search(r,
31: end for
32: (τ,p) - Sum (KKs. # p){})) R3
)=1)
33:
Return: æ.
of confidence intervals for all survived policies, which enables using the batch sizes in bandit algorithms [Perchet et al. 2016 Gao et al. 2019]
Besides, to obtain better regret bound, estimate the optimal value function at the end of each batch, and use it to build a tighter confidence region. As presented in Line 22 3 two empirical transition probabilities to construct the confidence region. Noting that the samples in the m-th batch independent of mn11, we could add a Bernstein-style constraint, where
a (n,
51
V(p.v)
34

---

6 Conclusion
In this paper, we study multi-batch reinforcement learning, and provide an efficient algorithm to achieve the near-optimal regret bound and batch complexity. It would be an interesting problem to generalize our results to reinforcement learning with function approximation case, e-g., linear MDP. Another important direction is to study the exact batch-regret trade-off for multi-batch reinforcement learning.
Broader Impact This work focus the theory of multi-batch reinforcement learning, and the
broader impact is not applicable.
References
Daniel Almirall, Scott Compton, Meredith Gunlicks-Stoesssee Naihua Duan, and Susan A Murphy, Designing a pilot sequential multiple assignment randomized trial for developing adaptive treatment strategy. Statistics in medicine, 31(17):1887-190) 2012.
Daniel Almirall, Inbal Wahum-Shamt Nancy E Sherwood, and Susan A Murphy. Introduction to smart designs for the development of adaptive interventions: with application weight loss research. Translational behavioral medicine, 4(3):260- 274, 2014.
Mohammad Gheshlaghi Azar, Rémi Munos, and Hilbert J Kappen. Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model. Machine learning, 91(3): 325-349, 2013.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pages 263-272. JMLR. org, 2017.
Yu Bai, Tengyang Xie, Nan Jiang, and Yu-Xiang Wang. Provably efficient q-learning with low switching cost. In Advances in Neural Information Processing Systems, pages 8004-801 2019.
Peter Bartlett and Ambuj Tewari. Regal: regularization based algorithm for reinforcement learning in weakly communicating mdps. In Proceedings of the 25th Conference Uncertainty in Artificial Intelligence (UAI 2009)). 2009.
Nicolo
Ofer Dekel, and Ohad Shamir. Online learning with switching costs and other adaptive adversaries. In Advances in Neural Information Processing Systems, pages 1 1660-1168,
2013.
Michael B Cohen, Yin Tat Lee, and Zhao Song. Solving linear programs in the current matrix multiplication time. Journal of the ACM (JACM), 68(1):1-39) 2021.
Christoph Dann, Lihong Li, Wei Wei, and Emma Brunskill. Policy certificates: Towards accountable reinforcement learning. In Proceedings of the 36th International Conference Machine Learn- ing, volume 97 of Proceedings of Machine Learning Research, pages 1507-1516, Long Beach, California, USA, 09-15 Jun 2019. PMLR.
Kefan Dong, Yingkai Li, Qin Zhang, and Yuan Zhou. Multinomial logit bandit with low switching cost. In International Conference on Machine Learning, pages 2607-2615. PMLR, 2020.
Minbo Gao, Tianle Xie, Simon S Du, and Lin F Yang. A provably efficient algorithm for linear markov decision process with low switching cost. arXiv preprint arXiv:2101.00494 2021.
Zijun Gao, Yanjun Han, Zhimei Ren, and Zhengqing Zhou. Batched multi-armed bandits problem. arXiv preprint arXiv: 00070006......... 2019.
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning, Journal of Machine Learning Research, (1[(App):15631166) 2010.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael Jordan. Is Q-learning provably efficient?
In Advances in Neural Information Processing Systems, pages 4863-4873, 2018
10

---

Sham M Kakade. On the sample complexity of reinforcement learning. PhD thesis, University of London London, England, 2003.
Sanjay Krishnan, Zongheng Yang, Ken Goldberg, Joseph Hellerstein, and Ion Stoica. Learning to optimize join queries with deep reinforcement learning. arXiv preprint arXiv:/808.03119 2018.
Huitan Lei, Inbal Nahum-Shani, Kevin Lynch, David Oslin, and Susan A Murphy. A" smart" design for building individualized treatment sequences. Annual review of clinical psychology, 8:21-48, 2012.
Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen. Breaking the sample size barrier in model-based reinforcement learning with a generative model. arXiv preprint wrXiv:2005.12900 2020.
Azalia Mirhoseini, Hieu Pham, Quoc Le, Benoit Steiner, Rasmus Larsen, Yuefeng Zhou, Naveen Kumar, Mohammad Norouzi, Samy Bengio, and Jeff Dean. Device placement optimization with reinforcement learning. In International Conference on Machine Learning, pages 8430-2439.
PMLR, 2017.
Vianney Perchet, Philippe Rigollet, Sylvain Chassang, Erik Snowberg, et al. Batched bandit problems. Annals of Statistics, 44(2):600661, 2016.
Dan Qiao, Ming Yin, Ming Min, and Yu-Xiang Wang. Sample-efficient reinforcement learning with loglog (t) switching cost. arXiv preprint arXiv:2202.06388 2022.
Yufei Ruan, Jiaqi Yang, and Yuan Zhou. Linear bandits with limited adaptivity and learning distributional optimal design. arXiv preprint arXiv:2007.01980, 2020.
David Simchi-Levi and Yunzong Xu. Phase transitions and cyclic phenomena in bandits with switching constraints. Available at SSRN 3380783, 2019.
Ming Yu, Zhuoran Yang. Mladen Kolar, and Zhaoran Wang. Convergent policy optimization for safe reinforcement learning. arXiv preprint arXiv: 2019.
Andrea Zanette and Emma Brunskill. Tighter problem-deeenddnt regret bounds in reinforcement learning without domain knowledge using value function bounds. In International Conference on Machine Learning, pages 0304-7312, 2019.
Zihan Zhang and Xiangyang Ji. Regret minimization for reinforcement learning by evaluating the optimal bias function. In Advances in Neural Information Processing Systems, pages 2823 2823-2832, 2019.
Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Almost optimal model-free reinforcement learning via reference-advantage decomposition. arXiv preprint w:Xi::2004.10019 2020.
Zihan Zhang, Xiangyang Ji, and Simon Du. Is reinforcement learning more difficult than bandits? near-optimal algorithm escaping the curse of horizon. In Conference on Learning Theory, pages 4528 4531. PMLR, 2021.


Reviews:
[{"review_id": "bgHx11XD4x", "reviewer": "Reviewer_jpiL", "summary": "The paper studies a batched reinforcement learning (RL) problem where the interaction is divided into $M$ epochs (‘batches’). The agent chooses the batch lengths before the interaction starts and can only update its policy at the beginning of a new batch. This setting is well-motivated in real-world applications where policies are deployed and adaptive/frequent policy updates are undesirable. As in the multi-armed bandit (MAB) problem, the authors show that any minimax algorithm must use $M=\\Omega(\\log\\log K)$ policy batches (where $K$ is the total number of episodes). They complement these lower bounds by proving a tight regret upper bound for a policy elimination algorithm that uses $M=H+\\log\\log K$ batches.", "questions": "Questions:\n* Why do you need two exploration stages?\n* Why do you need to use the confidence bounds for each next state separately, instead of the standard L1 bounds for the transition kernel? Is it due to the tightness requirement from the transition region? If so, can’t it be modified to allow these confidence intervals? It feels as if this is the main reason for the raw exploration stages.\n\n_____\n\nMinor/other comments (notice the numerous typos):\n* Definition 1 – the summation should end at $M$.\n* Theorem 1 – please move the footnote location – it looks like a power.\n* Line 116 – did you mean [N]?\n* Line 119  -a missing space before the citations.\n* Line 135 – variance of what?\n* Line 139 – after a batch, shouldn’t it be $N_h(s,a)\\approx d^{\\pi}(s,a) t^m$?\n* Line 165 – “by by”\n* The derivation in lines 176-177 wasn’t very clear.\n* I would also recommend putting more abstract algorithm blocks in the main paper, and leaving the detailed algorithm to the appendix.\n* Line 200 – delete “...such that $\\tilde{\\pi}\\in\\Pi$”.\n\n### Post-rebuttal\nI thank the authors for the response. \n\nI am sorry for the confusion - I of course meant that the initial stage requires knowing the number of episodes $K$, and not $H$ (which is a completely different setting). As I said, it is a minor issue.", "limitations": "I would have liked to see a more concrete discussion on the computational complexity of the algorithm – and not just O-notations", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I think that the framework is interesting and the results are nontrivial. Also, to the best of my knowledge, the algorithmic design is novel – while successive elimination algorithms are common in MABs, I am not familiar with (polynomial) SE algorithms in RL that eliminate in the transition space.\n\nOn the con side, the resulting algorithm is *very* complicated, uses numerous subroutines, each with its own computational complexity, and it is quite hard to understand its overall computational complexity (even if it’s polynomial). In general, I think that the paper was hard to follow, and its clarity could be improved. Another (minor) weakness is that the initial exploration stage requires knowing the horizon – it’s unclear whether the algorithm can be converted to an anytime algorithm.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "ZSFcyNrH2LR", "reviewer": "Reviewer_pfXX", "summary": "In this paper, this paper studies the episodic reinforcement learning (RL) problem modeled by finite-horizon Markov Decision Processes (MDPs) with constraints on the number of batches. It achieves near-optimal regret $O(\\sqrt{SAH^3K})$ using $O(H+\\log\\log(K))$ batches. The technical contribution includes a near-optimal design scheme to explore the unlearned states and a computationally efficient algorithm to explore certain directions with an approximated transition model.", "questions": "The writing of the paper requires significant improvement. Concretely, see my comments in above.", "limitations": "Yes.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**: On the technique ends, I think this paper provides some solid contribution to achieving near-optimal regret, In particular, Lemma 1 leverages a G-optimal design style result for offline reinforcement learning and the proof is delicate. In addition, the decomposition (34) is critical for achieving tight regret with the term T2 can be bounded as a higher-order term. However, there are a few aspects that affect the quality of this paper.\n\n**Weaknesses**:\n\n1. The writing is not professional. There are numerous parts that are unclear. See the following.\n\n2. the value of $k_1=\\sqrt{SAKH}$ would deteriorate the the claimed dependence of $\\sqrt{H^3}$ in regret. Raw exploration will become the dominant term and would make the bound has order $\\sqrt{H^5}$.\n\n3. Lemma 4 seems to be inconsistent with Lemma 4 (restated).\n\n4. The equation in line 582 is not accurate since $P^{h'}$ is population-level quantities.\n\n5. equation (52) seems to be wreak havoc, also equation (54).\n\n6. Also, line 617-622 seems disconnected.", "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": "7Q2WbaglQz0", "reviewer": "Reviewer_gMzA", "summary": "This paper studies multi-batch reinforcement learning in the finite-horizon MDPs. They propose an algorithm that achieves near-optimal regret bound $O(\\sqrt{SAH^3K})$ in $K$ episodes using only $O(H + \\log_2\\log_2K)$ batches. They also show a nearly matching lower bound stating that in order to achieve $O(\\text{poly}(S, A, H)\\sqrt{K})$ regret, the number of batches is at least $\\Omega(H/\\log_A(K) + \\log_2\\log_2K)$.", "questions": "1. Is the overall algorithm computationally efficient? The authors address this question for some component of their algorithm but does not mention the overall computation complexity. The name \"policy elimination\" seems to suggest that it is computationally inefficient, but the pseudo code does not seem to contain computationally inefficient components. A clarification on this would be useful.\n2. Is there any potential way to simplify the algorithm?\n3. Why is EVI not enough for policy search?", "limitations": "There are several typos:\n1. Definition 1: $\\sum_{m=1}^Kt_m$\n2. Equation (2): missing $p$\n3. line 163: double \"by\"", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: the problem studied in this paper is very important and has significant practical values. The proposed algorithm has a strong theoretical performance that nearly matching the lower bound. There are also several non-trivial technical contributions in this paper.\n\nWeakness: the final algorithm is fairly complicated and hard to follow. My suggestion is that the author should spend more paragraphs on discussing the algorithm design, and postpone the proof sketch to Appendix. Discussion on why existing approaches achieve sub-optimal results, what are the challenges, and how each component of this paper tackle these challenges would be very helpful for the readers to appreciate the contributions of this paper.", "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": "61IkiBW7CE", "reviewer": "Reviewer_YiLt", "summary": "Authors propose a novel algorithm for multi-batch reinforcement learning with nearly minimax optimal regret and $O(H + \\log\\log K)$ batch complexity. Additionally, authors propose polynomial time implementation, and provide a lower bound on batch complexity of order $\\Theta(H/\\log_A(K) + \\log \\log K)$ to show that their algorithm is nearly optimal in this parameter too.", "questions": "1) In the main paper there is a lack of intuition how algorithm achieves such a small batch complexity as $O(H + \\log \\log K)$, whereas it seems to be one of the most crucial points of the proposed algorithm. It would be great to see such an intuition.\n\n2) Additionally, it would be very interesting to see the full computational complexity of the algorithm and a more direct description on the places inside the algorithm where new batch starts;\n\nAdditionally, there are several typos was notices and needs to be fixed\n\n- Line 78: Typo in asymptotic;\n- Line 107: Wrong indexes in the definition of V- and Q-functions;\n- Line 123: missing p in the definition of lower bound;\n- Line 163: double “by”\n- Line 492: formatting problems with the table of notation; lack of important notation in this table such as $W(v, p)$.\n- Line 598: strange line break that makes formula unreadable;\n- Line 617,618: broken links to Proposition and Lemma.", "limitations": "Authors addressed all the limitations of their work.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1) The setting of multi-batch RL is seems to be very valuable in the modern RL community and up to my knowledge it is the first theoretical result in this sphere;\n\n2) Nearly optimal regret bound in the first term and nearly optimal batch complexity; iterated logarithm of policy switches sounds to be very interesting even in a simpler setting of counting the number of policy switches.\n\n3) Provided lower bound to strengthen the result on batch complexity;\n\nWeaknesses:\n\n1) Whereas the setting of multi-batch RL is interesting in applications, the proposed algorithm is seems to be impossible to implement beyond tabular setting due to policy elimination structure;\n\n2) In the main paper there is no mentioned exact computational complexity of the algorithm, only the fact that it is polynomial; In the algorithm description we may see that the algorithm needs to take a loop over $K^3$ elements, that make the computation complexity enormous at least on one stage of the algorithm.\n\n3) Not very good dependence on a number of states in second-order terms; It seems that the regime of nearly minimax optimality of this algorithm appears only after $K \\geq S^{12} A^{8} H^{24}$ (to make the first-order regret term greater than the third one).\n\n4) Hard-to-follow description of the algorithm both as a pseudo-code and as a text description.", "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