A Boosting Approach to Reinforcement Learning
Authors: Nataly Brukhim
Elad Hazan
Karan Singh
Venue: ICLR 2022 Submitted (2022)

Abstract: We study efficient algorithms for reinforcement learning in Markov decision processes, whose complexity is independent of the number of states. This formulation succinctly captures large scale problems, but is also known to be computationally hard in its general form.
    Previous approaches attempt to circumvent the computational hardness by assuming structure in either transition function or the value function, or by relaxing the solution guarantee to a local optimality condition.

    We consider the methodology of boosting, borrowed from supervised learning, for converting weak learners into an effective policy. The notion of weak learning we study is that of sampled-based approximate optimization of linear functions over policies. Under this assumption of weak learnability, we give an efficient algorithm that is capable of improving the accuracy of such weak learning methods iteratively. We prove sample complexity and running time bounds on our method, that are polynomial in the natural parameters of the problem: approximation guarantee, discount factor, distribution mismatch and number of actions. In particular, our bound does not explicitly depend on the number of states.

    A technical difficulty in applying previous boosting results, is that the value function over policy space is not convex. We show how to use a non-convex variant of the Frank-Wolfe method, coupled with recent advances in gradient boosting that allow incorporating a weak learner with multiplicative approximation guarantee, to overcome the non-convexity and attain global optimality guarantees.

Under review as a conference paper at ICLR 2022
A BOOSTING LEARNING
APPROACH TO REINFORCEMENT
Anonymous authors Paper under double-blind review
ABSTRACT
We study efficient algorithms for reinforcement learning in Markov decision pro- cesses, whose complexity is independent of the number of states. This formulation succinetly captures large scale problems, but also known to be computationally hard in its general form. Previous approaches attempt circumvent the compu- tational hardness by assuming structure in either transition function or the value function, or by relaxing the solution guarantee to local optimality condition.
We consider the methodology of boosting, borrowed from supervised learning, for converting weak learners into an effective policy. The notion of weak learning we study is that of sampled-based approximate optimization of linear functions over policies. Under this assumption of weak learnability, we give an efficient algo- rithm that is capable of improving the accuracy of such weak learning methods iteratively. We prove sample complexity and running time bounds on our method, that are polynomial in the natural parameters of the problem: approximation guar- antee, discount factor, distribution mismatch and number of actions. In particular, our bound does not explicitly depend on the number of states.
A technical difficulty in applying previous boosting results, is that the value func- tion policy space is not convex. We show how the Frank- Wolfe method, coupled with recent advances in gradient boosting that allow incorporating weak learner with multiplicative approximation guarantee, to overcome the non-convexity and attain global optimality guarantees.
non-comvex variant of
INTRODUCTION
The field of reinforcement learning, formally modelled as learning in Markov decision processes (MDP), models the mechanism of learning from rewards, opposed to examples. Although the case of tabular MDPs is well understood, the main difficulty in applying RL to practice is the size of the state space.
Various techniques have been suggested and applied to cope with very large MDPs. The most common of which is function approximation of either the value or the transition function of the underlying MDP, many times using deep neural networks. Training deep neural networks in the supervised learning model known be computationally hard. Therefore reinforcement learning with neural function approximation is also computationally hard in general, and for this reason lacks provable guarantees.
This challenge of finding efficient and provable algorithms for MDPs with large state space is the focus of our study. Previous approaches can be categorized terms of the structural assumptions made on the MDP to circumvent the computational hardness. Some studies focus on structured dynamics, whereas others on structured value function or policy classes w.r.t. to the dynamics.
In this paper study another methodology to derive provable algorithms for reinforcement learn- ing: ensemble methods for aggregating weak or approximate algorithms into substantially more accurate solutions. Our method can be thought of as extending the methodology of boosting from supervised learning (Schapire & Freund| (012)) to reinforcement learning. Interestingly, however, resulting aggregation of weak learners not linear.
In order to circumvent the computational hardness of solving general MDPs with function approx- imation, assumes access to weak learner: efficient sample-based procedure that is capable

---

Under review as a conference paper at ICLR 2022
of generating approximate solution any linear optimization objective over the space of poli- cies. We describe an algorithm that iteratively calls this procedure on carefully constructed new objectives, and aggregates the solution into single policy. We prove that after sufficiently many iterations, our resulting policy is provably near-optimal.
1.1 CHALLENGES AND TECHNIQUES
Reinforcement learning is quite different from supervised learning and several difficulties have to be circumvented for boosting to work. Amongst the challenges that the reinforcement learning setting presents, consider the following.
(a) The value function is not convex concave function of the policy. This is true even in the tabular case, and even more so if we use a parameterized policy class.
(b) The transition matrix is unknown, or prohibitively large to manipulate for large state spaces. This means that even evaluation of a policy cannot be exact, and only be computed approximately.
(c) It is unrealistic to expect weak learner that attains near-optimal value for given linear objective over the policy class. At most one can hope for multiplicative and/or additive approximation of the overall value.
Our approach overcomes these challenges by applied several new well as recently developed techniques. To overcome the nonconvexity the value function, we use a novel variant of the Frank-Woie optimization algorithm that simultaneously delivers two guarantees. First, it finds first order stationary point with near-optimal rate. Secondly, the objective happens to admit a cer- tain gradient domination property, an important generalization of convexity, also guarantees optimal value. The application of the nonconvex Frank-Won Wolfe method is justified due to previous recent investigation of the policy gradient algorithm (Agarwal et al. 2019 2020a). which identified conditions under which the value function is gradient dominated.
The second informatiion-heorrticc challenge of the unknown transition function is overcome by care- ful algorithmic design: our boosting algorithm requires only samples of the transitions and rewards. These are obtained by rollouts on the MDP.
The third challenge is perhaps the most difficult to overcome. Thus far, the use of the Frank-Wolfe method in reinforcement learning did not include multiplicative approximation, which critical for our application. Luckily, recent work in the area of online convex optimization (Hazan & Singh, 202T) studies boosting with a multiplicative weak learner. We make critical use of this new technique which includes non-linear aggregation (using 2-layer neural network) of the weak learners. This aspect perhaps of general interest to boosting algorithm design, which is mostly based on linear aggregation.
1.2
OUR CONTRIBUTIONS
Our main contribution is a novel efficient boosting algorithm for reinforcement learning. The input to this algorithm is a weak learning method capable of approximately optimizing a linear function over certain policy class.
The output of the algorithm is policy which does not belong to the original class considered. It is rather a non-linear aggregation of policies from the original class, according to a two-layer neural network. This is result of the two-tier structure of our algorithm: outer loop of non-convex Frank- Wolfe method, and an inner loop of online convex optimization boosting. The final policy comes with provable guarantees against the class of all possible policies.
Our algorithm and guarantees come in four flavors, depending on the mode of accessing the MDP (two options), and the boosting methodology for the inner online convex optimization problem (two options).
It is important to point out that study the question from optimization perspective, and hence, assume the availability of an efficient exploration scheme - either via access to a reset distribution that has some overlap with the state distribution of the optimal policy, or constraining the policy
2

---

Under review as a conference paper at ICLR 2022
Supervised weak learner
Online weak learner
Episodic model
Ch (1))/a²'
C (T))/aa
Co max
d=
Rollouts w. v-resets
D
d"
Table I: Sample complexity of the proposed algorithms for different a-weaa learning models (su- pervised online) and modes of accessing the MDP (rollouts & rollouts with reset distribution v)), suppressing polynomial factors in |A], 1/(1 7). See Theorem 11 for details.
class to policies that explore sufficiently. Such considerations also arise when reducing reinforce- ment learning to a sequence supervised learning problems, e.g. Conservative Policy Iteration (Kakade & Langford 2002) assumes the former. One contribution make here is quantita- tively differentiate between these two modes exploration in terms of the rates of convergence they enable for the boosting setting.
1.3 RELATED WORK
To cope with prohibitively large MDPs, the method of choice to approximate the policy and transi- tion space are deep neural networks, dubbed "deep reinforcement learning". Deep RL gave rise to beyond human performance in games such as Go, protein folding, as well as near-human level au- tonomous driving. In terms of provable methods for deep RL, there first is a robust analysis of the policy gradient algorithm (Agarwal et al., 2019 2020a). Importantly, the gradient domination property of the value function established in this work is needed in order to achieve global convergence guarantees of our boosting method.
main lines of work. The
The other line of work for provable approaches is policy iteration, which uses restricted policy class, making incremental updates, such as Conservative Policy Iteration (CPI) (Kakade & Langford 2002 Scherrer & Geist 2014), and Policy Search by Dynamic Programming (Banella al.
2003
Our boosting approach for provable deep RL builds on the vast literature of boosting for supervised
learning (Schapire & Freund 2012). and recently online learning (Leistner et al. 2009 Chen et al., 2012 2014 Beygelzimer al. [0133] Jung et al. 2017:: Jung Tewari 2018). One the crucial techniques important for our application is the extension of boosting to the online convex optimiza- tion setting, with bandit information (Brukhim & Hazan 202T), and critically with a multiplicative weak learner (Hazan & Singh, 2021). This latter technique implies a non-linear aggregation of the weak learners. Non-linear boosting was only recently investigated in the context of classification (Alon et al. 2020), where it shown to potentially enable significantly more efficient boosting.
Perhaps the closest work to ours boosting in the context of control of dynamical systems (Agar- wal et al. 2020b). However, this work critically requires knowledge of the underlying dynamics (transitions), which we do not, and cannot cope with multiplicative approximate weak learner.
The Frank-Wolfe Wolfe algorithm is extensively used in machine learning, see e.g. (Jggi 2013), refer- ences therein, and recent progress in stochastic Frank- Wolfe methods (Hassani et al. (2117 Mokhhari al. 2018 Chen al. 2018 Xie et al., 2019). Recent literature has applied variant of this algo- rithm to reinforcement learning in the context of state space exploration (Hazan et al. 2019).
2 PRELIMINARIES
Optimization. We say that a differentiable function f KC + RR over some domain KC is L-smooth with respect to some norm
|]. if for every y K. we have
ff() - f(x) - vf(x) x))
-
1| r v112.
2
3

---

Under review as a conference paper at ICLR 2022
For constrained optimization (such over A the projection r: : FRIAI AA of point onto a domain A is
arg min || y/1-
An important generalization of convex function we use henceforth is that of gradient domination, Definition 1 (Gradient Domination). A function
K. I is said to be (K, T, K1, K2 -loclll gradient dominated (around K by K2)) for all a Kr, it holds that
max f(y) f(x) I K x max (Vf(z) (y 2)} +T. yEK.
yER₂
Markoy decision process. An infinite-horizon discounted Markov Decision Process (MDP) M (S, A, 7; is specified by: a state space S, an action space A, a transition model P where P(s"ls,)) a) denotes the probability of immediately transitioning to state s' upon taking action a at state s, a reward function S x A [0, where r(s, a) is the immediate reward associated with taking action at state a discount factor E [o, 1); starting state distribution d over S. For any infnitt--ength state-action sequence (hereafter, called a trajectory). we assign the following value
V(T = (so; 0o, a1....))
Σ y rr((,,,)) 1=0
The agent interacts with the MDP through the choice of stochastic policy + A it exe- cutes, where Aa denotes the probability simplex over A. The execution of such a policy induces distribution over trajectories (Su, ag.....
P(T = ds()
II t=0
(1)
Using this description we can associate state (s) and state-action (" a) value function with any policy æ. For an arbitrary distrbution d over S, define:
(s) E Σ 7'r(s,,, ar)
T,, 80 = s,
= (-s [Q" (s, s)]
V = Espad (V)(s)
Here the expectation is with respect to the randomness the trajectory induced by x in M. When convenient, we shall use 4 to denote Vł,- and V to denote max, !*5
Similarly, to any policy n, one may ascribe a (discounted) state state- visitation distribution d= = dz.-
=1=)=(190) Σ
Σ TiR
P(T|T, 80 dd
Modes of Accessing the MDP. We henceforth consider modes of accessing the MDP, that standard in the reinforcement learning literature, and provide different results for each.
The first natural access model is called the episodic rollout setting. This mode of interaction allows us to execute policy, stop and restart at any point, and do this multiple times.
Another interaction model consider is called rollout with y-restarts. This is similar to the episodic setting, but here the agent may draw from the MDP trajectory seeded with an initial state distribution // + dg. This interaction model was considered in prior work on policy optimization Kakade & Langford (2002); Agarwal et al. (2019). The motivation for this model is two-fold: first, can used to incorporate priors (or domain knowledge) about the state coverage of optimal policy; second, provides mechanism to incorporate exploration into policy optimization procedures.
SETTING: POLICY AGGREGATION AND WEAK LEARNING
Our boosting algorithms henceforth call upon weak learners to generate weak policies, and aggre- gate these policies way that guarantees eventual convergence to optimality. this section we formalize both components.
4

---

Under review as a conference paper at ICLR 2022
A Policy Tree E N,T)
112
[[
1 12
A
X
Shrub A E AIL,
W1
712
77-4 77. 716
Figure I: The figure illustrates a Policy Tree hierarchy (see Definition obtained by setting N on the inner loop, and T' = on the outer loop, to overall get all base policies Ti...., Te E Ul on the lower level. The middle level holds T 2 Policy Shurbs (see Definition 4p, where each Shrub d E A(I, is an aggregation of base policies. The top level is an weighted aggregation of the projected shrubs r[Ae]. which forms the overall Policy Tree E MMII, N,T).
3.1 POLICY AGGREGATION
For base class of policies Il, our algorithm incrementally builds a more expressive policy class by aggregating base policies via both linear combinations and non-linear transformations. In effect, the algorithm produces a finite-width depth-2 circuit over some subset of the base policy class. We start with the simpler linear aggregation.
Definition 2 (Function Aggregation). Given some No Z4, IR, (fi,... SNO) (S RI we define f = - wnfn to be the unique function f : IR for which simultanc- ously for all S, it holds
No Σ wn (s).
f(s)
Next, the projection operation below may be viewed as a non-linear activation, such as ReLU, in deep learning terms. Note that the projection of any function from S to RIAI produces policy, i.e. a mapping from states to distributions over actions.
Definition (Policy Projection). Given function to be a policy such that simultancously for all E S, it holds that (T-1s) = [f(ss))
|| define projected policy [[f]
The next definition defines the class of functions represented by circuits of depth over base policy class. Note that these function do not necessarily represent policies since they take an affine (vs. convex) combination policies.
Definition (Shrub). For an arbitrary base policy class C A., define AIII, N) be set such that X E (II, N) if and only if there exists No s N, w E RR (T),... N.) E 1o such that X No Wn
The final definition describes the set of possible outputs of the boosting procedure.
Definition (Policy Tree). For an arbitrary base policy class IT C S + A define M[TI, N, T) to be a policy class such that ग E U1(1,, N, I') and only there exists To < T, w E AT, (A1, "'i,...Amy Ar.) e AIII, NN To such that = ETe [.A]]
is important that the policy that the boosting algorithm outputs can be evaluated efficiently, In the appendix show it is indeed the (see Lemma 15

---

Under review as a conference paper at ICLR 2022
3.2 MODELS OF WEAK LEARNING
We consider two types of weak leamers, and give different end results based on the different as- sumptions: weak supervised and weak online learners. In the discussion below, let n. be uniformly random policy, i.e. V(s, a) E S x A, (a(s) = 1/
Supervised Learning. The natural way define weak learning is an algorithm whose perfor- mance is always slight better than that of random policy, one that chooses an action uniformly at random any given state. However, in general no learner can outperform a random learner over all label distributions (this is called the "no free lunch" theorem). This motivates the literature on agnostic boosting (Kanade & Kalai 2009 Brukhim et al. 2020 Hazan & Singh (02T)) that defines weak learner
that can approximate the best policy
given policy class.
Definition (Weak Supervised Learner). Let a E (0, 1). Consider a class L. of linear loss functions
e R R. and DD a family of distributions that are supported over S x L. policy classes Iw,, II. A weak supervised learning algorithm, for every e, > O, given m(s, 6) samples Dm from any distribution D IN outputs policy W(Dm) E 1l such that with probability 1-
E(s,))=D ((W(()))((((Dm)))
max (s.0)= ( ((TT"() (s)) + (1 (., -))(,.)D)((((((())) -E. a ="Elf
Note that the weak learner outputs a policy in Hw which is approximately competitive against the class II. As an additional relaxation, instead of requiring that the weak learning guarantee holds for all distributions, in our setup, it will be sufficient that the weak learning assumption holds over natural distributions. We define these below. Hereafter, we refer to NN, T) as U1 for N, = O(poly (1 -- a- log 8 I)) specified later.
Assumption (Weak Supervised Learning). The booster has access to a weak supervised learning oracle (Definition 6 over the policy class II. for some a E (0, 1). Furthermore, the weak learning condition holds only for class of natural distributions D D E D if and only if there exists some π such that
Ds(s) J ((s,))dp(()) d (s).
In particular, while a natural distribution may have arbitrary distribution over labels, its marginal distribution over states must be realizable the state distribution of some policy in over the MDP M. Therefore, the complexity of weak learning adapts to the complexity of the MDP itself. As an extreme example, in stochastic contextual bandits where policies do affect the distribution of states (say do). it is sufficient that the weak learning condition holds with respect to all couplings of a single distribution do-
Online Learning. The second model of weak learning we consider requires stronger assumption, but will give us better sample and oracle complexity bounds henceforth.
Definition 7 (Weak Online Learner). Let (0, 1). Consider class L of linear loss functions é: A + IR. A weak online learning algorithm, for every M > 0, incrementall for each timestep computes policy Wm. Iw and then observes the state-loss pair (s, S L such that
Σ em em((" + (1-a)
Σ (TT(T( Rw)(M).
MAx 3E" EII
Assumption (Weak Online Learning). The booster has access to a weak online learning oracle (Definition 7 over the policy class IT, for some E (0,1).
Remark 8. A similar remark about natural distributions applies to the online weak learner. In par- ticular, sufficient the guarantee in 7 holds for arbitrary sequence of loss functions with high probability over the sampling of the state from d= for some π n. Although stronger than su- pervised weak learning, this oracle can be interpreted as relaxation the online weak learning oracle considered in (Brukhim et al. 2020 Brukhim & Hazan 2021 Hazan & Singh 2021). A sim- ilar model of hybrid seerssriil-stoccaaeee
online learning was considered in (Rakhlin et al.) 2011 Lazaric & Munos 2009| Beygelzimer al. (0011). In particular, it is known (Lazaric & Munos, 2009) that unlike online learning, the capacity of a hypothesis class for this model is governed by its VC dimension (vs. Littlestone dimension).

---

Under review as a conference paper at ICLR 2022
4 ALGORITHM & MAIN RESULTS
In this section we describe our RI. boosting algorithm. Here we focus on the case where supervised weak learning is provided. The online weak learners variant of our result is detailed in the appendix. We next define several definitions and algorithmic subroutines required for our method.
operate overs functions The Extension Operator. The extension operator (Hazan & Singh 202
and modifies their value outside and near the boundary of the convex set A to aid the boosting algorithm.
Fa.e(f((z)=
min yEAA
f(y) +
min SEAA
y
x||
yl1
23
To state the results, we need the following definitions. The first generalizes the policy completeness notion from (Scherrer & Geist (2014). It may be seen the policy-equivalent analogue of inherent bellman error (Munos & Szepesvári 2008). Intuitively, it measures the degree to which a policy in II can best approximate the bellman operator an average sense with respect to the state distribution induced by a policy from IT. Definition 9 (Policy Completeness). For any initial state distribution μ4, define
(UI, II) = max min Bewdy rEn E
max
(s, (11)
The following notion of the distribution mismatch coefficient often useful to characterize the exploration problem faced by policy optimization algorithms.
Definition 10 (Distribution Mismatch). Let x² arg max, VF, and fixed initial state distribu- tion (see section 2p. Define the following distribution mismatch coefficients
d=
d
Cos (n)
max SEn
Dx
=
d
4.1 RL BOOSTING VIA WEAK SUPERVISED LEARNING
We give the main RL boosting algorithm, assuming supervised weak learners. We use a simple sub-routine for choosing step size, provided in the appendix.
Algorithm RL Boosting via Weak Supervised Learning
1: Input parameters T, N, M, f p. Initialize a policy zu E Iw arbitrarily.
2: for = 1 to 7 do
3: Set Pr.o to be an arbitrary policy in Ilw.
4: for 1 to do
5: Execute πt-1 for M episodes with initial state distribution via Algorithm 2 to get
Dr, [s Q.
6:
Modify Dr,,. to produce a new dataset Dú,, = {ss, fi) such that for all E [m]]
fr = -Va. - (p.
7:
Let Ar, be the policy chosen by the weak learning oracle when given data set D Update Pt,n = (1 Pt,n))t A 12.m 1) Tr.
8:
9:
end for
Declare oi I I
Choose M1, min 1, 2C pf do else n1, = StepChooser(At-111 ,, P). m1 7z
11:
12: Update
13:
end for
14:
Output π=mT if μr do else output ग with the smallest 77.
For brevity, We the shorthand Coc where clear from context.

---

Under review as a conference paper at ICLR 2022
Theorem 11. Algorithm
samples T(MN + P) episodes of length Ō with probability 1 - 6.
In the episodic model, for 0
C N 16|A Co. (1-1)
2
M
(1-2)"as
Coc |1] NT ) do.
(1 [1-18'
P = O, with probability 8,
- v S Coo
1 1-7 +E.
In the v-reset model, for (1-7)0e2
8D N. =
= Ō
2001A11 M = (1-7)822
(1->)9ac
(1-7Pac 8AIDx ENT ) v, with probability -
m
--- V S Doo 7)² t
4.2 TRAJECTORY SAMPLER
In Algorithm we describe an episodic sampling procedure, that is used in our sample-based RL boosting algorithms described above. For fixed initial state distribution μu, and any given policy т, we apply the following sampling procedure: start at an initial state Sq ~ μe, and continue to thereafter in the MDP according any policy म, until termination. With this process, it is straightforward to both sample from the state visitation distribution s d", and to obtain unbiased samples of Q" (s, )); Algorithm for the detailed process.
Algorithm 2 Trajectory Sampler: ~ d", unbiased estimate of Q"
1: Sample state 8g ~ μl, and action a' ~ ((()) uniformly.
2: Sample
d as follows: every timestep h, with probability 7, according to æ; else, accept 8;, as the sample and proceed to Step 3.
3: Take action a' at state 8h, then continue execute æ, and use termination probability of -- Upon termination, set R(ss, a') as the undiscounted sum of rewards from time h onwards.
4: Define the vector Q7, such that for all A, Q7, (a) |A| R(sh, a') Iaza'
5: return (sh, )-
5 ANALYSIS PROOF SKETCH
We sketch the high-level ideas of the proof of our main result, stated in Theorem I1 and refer the reader the appendix for the formal proof. Throughout the analysis, we use the notation V, V to denote the gradient of the value function with respect to the |S] [Al-sized representation of the policy π, namely the functional gradient of V
We establish an equivalence between the outlined algorithm and an abstraction of the Frank-Wolf algorithm (Algorithm D from optimization theory. This variant of the Frank-Woll (FW) algo- rithm operates over non-convex and gradient dominated functions to obtain the following novel convergence guarantees. We establish the necessary gradient domination results from the policy completeness results.
H Hbbuunded, and the diameter of IC in ||- ||. be D. Then, for (eo, (2) -lineer optimization oracle, the oulput Tt of Algorithm D satisfies
Theorem 12. Let f K be L-smooth in some norm || -
(f -u-a x S <vv V 22HL2
max K
+ +
T
Furthermore, f is (K, T, K2, K22 -locally gradient-dominat and Io.... Ey E K2, then it holds HH
f(x=((x=)))))))rr))) f(t) < 2n.2 max max{LD LD?,H,
max eK:
+ + KEg.
T
The Trank-Wolff algorithm utilizes inner gradient optimization oracle a subroutine. To imple- ment this oracle using approximate optimizers, we utilize yet another variant of the FW method as "internal-boostin for the weak learners (by employing adapted analysis of Theorem 13
8

---

Under review as a conference paper at ICLR 2022
5.1 INTERNAL-BOOSTINE WEAK LEARNERS
We utilize a variant of the Frank-Wolfe method as a form "internal-boosting" for the weak learners, by employing adapted analysis of previous work that is stated below.
Note that Q' produced by Algorithm satisfies (s.-))
|4| 1-y" We can now borrow the
following result on boosting for statistical learning from (Hazan & Singh 202T), specializing the
decision set to be A. Let Dj be the distribution induced by the trajectory sampler in round t.
Theorem 13 ((Hazan & Singh, 2021).. b). Let V a.v. and 1/2,
min 1}. Then, for any m..
produced by Algorithm 7 satisftes with probability 5 that
2/AA|
max E (..O) [QT [()] (() Q2= x(((s]
$
+
#Ell
(1 (1-7)a
VN
5.2 FROM WEAK LEARNING LINEAR OPTIMIZATION
In the following Lemma, we give an important observation which allows us to re-state the guarantee the previous subsection in terms of linear optimization over functional gradients.
Lemma 14. Applying Algorithm for any given policy n, yields an unbiased estimate of the gradi- ent, such that for any n',
1-7 B ( 1
V (VVV T 1
x (11))]
where n 7-18)) E A, and D the distribution induced on the oulputs of Algorithm for given policy π. and initial state distribution p..
Proof. Recall V V denotes the gradient with respect to the |S] x A Al-sided representation of the policy π the functional gradient. Then, using the policy gradient theorem (Williams) 1992 Sutton et al. 2000), it is given by.
OV (a(a)) 1-7 d (=)
(3)
The following sources of randomness are at play in the sampling algorithm (Algorithm 2): the distribution d' (which encompasses the discount-factor probability, and the stochasticity of I)) and the uniform sampling over A. For fixed s, n, denote by O as the distribution over (s,-) )) To conclude the claim, observe that by construction
random termination, the transition
RAA, induced by all the aforementioned randomness sources.
E Exr (A")) )), Q**((
(4)
CONCLUSIONS
Building on recent advances in boosting for online convex optimization and bandits, we have de- scribed boosting algorithm for reinforcement learning over large state spaces with provable guaran- tees. see this as a first attempt at using a tried-and-tested methodology from supervised learning in RL, and many challenges remain.
First and foremost, our notion of weak learner optimizes a linear function over policy space. A more natural weak learner would be RL agent with multiplicative optimality guarantee, and it would be interesting to extend our methodology to this notion weak learnability.
Another important aspect that is not discussed in our paper is that of state-space exploration. Poten- tially boosting can be combined with state-space exploration techniques to give stronger guarantees independent of distribution mismatch Coc. Dx factors.
Finally, a feature of our method is that it produces nonlinear aggregations of weak learners as per a two layer neural network. Are simpler aggregations with provable guarantees possible?

---

Under review as a conference paper at ICLR 2022
REFERENCES
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradi- ent methods: Optimality, approximation, and distribution shift, arXiv preprint arXiv: 2019.
Alekh Agarwal, Mikael Henaff, Sham Kakade, and Wen Sun. Pe-pg: Policy cover directed explo- ration for provable policy gradient learning. arXiv preprint arXiv:2007.08459 2020a.
Naman Agarwal, Nataly Brukhim, Elad Hazan, and Zhou Lu. Boosting for control of dynamical systems. In International Conference on Machine Learning, pp. 96-103, PMLR, 2020b.
Noga Alon, Alon Gonen, Elad Hazan, and Shay Moran. Boosting simple learners. arXiv preprint arXiv:2001.11704, 2020.
J Andrew Bagnell, Sham Kakade, Andrew Y Ng, and Jeff G Schneider. Policy search by dynamic programming. In Advances in Neural Information Processing Systems, 2003.
Alina Beygelzimer, John Langford, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandit algorithms with supervised learning guarantees. In Proceedings of the Fourteenth International Conference on Artificial Intellience and Statistics, pp. 19-26. JMLR Workshop and Conference Proceedings, 2011.
Alina Beygelzimer, Satyen Kale, and Haipeng Luo. Optimal and adaptive algorithms for online boosting. In International Conference on Machine Learning, pp. 2323-2331, 2015.
Nataly Brukhim and Elad Hazan. Online boosting with bandit feedback. In Algorithmic Learning Theory, pp. 397-420. PMLR, 2021.
Nataly Brukhim, Xinyi Chen, Elad Hazan, and Shay Moran. Online agnostic boosting via regret minimization. In Advances in Neural Information Processing Systems, 2020.
Lin Chen, Christopher Harshaw, Hamed Hassani, and Amin Karbasi. Projection- free online opti- mization with stochastic gradient: From convexity to submodularity. In International Conference Machine Learning, pp. 814 123, 2018.
Shang-Tse Chen, Hsuan- Tien Lin, and Chi-Jen Lu. An online boosting algorithm with theoretical justifications. In Proceedings of the 29th International Coference International Conference Machine Learning, pp. 1873-1880, 2012.
Shang- Tse Chen, Hsuan-Tice Tien Lin, and Chi-Jen Lu. Boosting with online binary learners for the multiclass bandit problem. In International Conference on Machine Learning, pp. 342-350, 2014.
John Duchi, Shai Shwarr, Yoram Singer, and Tushar Chandra. Efficient projections onto the I b-ball for learning in high dimensions. In Proceedings of the 25th international conference on Machine learning, pp. 272-279, 2008
Hamed Hassani, Mahdi Soltanolkotabi, and Amin Karbasi. Gradient methods for submodular max- imization. In Advances in Neural Information Processing Systems, pp. 5841-5851, 2017.
Elad Hazan. Introduction to online convex optimization. arXiv preprint arXiv: 2019.
Elad Hazan and Karan Singh. 00X0052002.09355. 2021.
Boosting for online convex optimization.
arXiv preprint
Elad Hazan, Sham Kakade, Karan Singh, and Abby Van Soest. Provably efficient maximum entropy exploration. International Conference on Machine Learning, pp. 2681-2691. PMLR, 2019.
Martin Jaggi. Revisiting frank-wolfe: Projection-free sparse convex optimization. In International Conference on Machine Learning, pp. 427-435. PMLR, 2013.
Young Hun Jung and Ambuj Tewari. Online boosting algorithms for multi-label ranking. In Inter- national Conference Artificial Intelligence and Statistics, pp. 279-287, 2018.
10

---

Under review as a conference paper at ICLR 2022
Young Hun Jung, Jack Goetz, and Ambuj Tewari. Online multiclass boosting. In Advances in neural information processing systems, pp. 919,928,20 2017.
Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In In Proc. 19th International Conference on Machine Learning. Citeseer, 2002.
Varun Kanade and Adam Kalai, Potential-based agnostic boosting. In Advances in neural informa- fion processing systems, pp. 880-888, 2009.
Alessandro Lazaric and Rémi Munos. Hybrid stochastic-adversane on-line learning. In Conference on Learning Theory, 2009.
Christian Leistner, Amir Saffari, Peter M Roth, and Horst Bischof. On robustness of on-line boosting-a competitive study. In IEEE 12th International Conference Computer Vision Work- shops, ICCV Workshops, pp. 1362-1369, IEEE, 2009.
Aryan Mokhtari, Hamed Hassani, and Amin Karbasi. Stochastic conditional gradient methods: From convex minimization to submodular maximization. arXiv preprint arXiv: IrXiv:1804.0000 8804.09554, 2018.
Rémi Munos and Csaba Szepesvári. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 9(5), 2008.
Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online learning: Stochastic and strained adversaries. arXiv preprint arXiv:1104.5070 2011.
Robert E Schapire and Yoav Freund. Boosting: Foundations and Algorithms. MIT Press, 2012.
Bruno Scherrer and Matthieu Geist. Local policy search in convex space and conservative pol- icy iteration as boosted policy search. Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 35-50. Springer, 2014.
Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradi- ent methods for reinforcement learning with function approximation. In S. Solla, T. Leen, and K. Müller (eds.), Advances in Neurul Information Processing Systems, volume 12. MIT Press, 2000. URL /RRL//tcss//pprcciisss.eeeer ieeueeeeeeddd.g................. wttpap/ee//9////1....e.e/ BB662D88DDDeeeeeeeee00000-----p2 pdf
Ronald J Williams. Simple statistical gralient-fllooingg algorithms for connectionist reinforcement learning. Machine learning, 8(3-4):229 1992.
Jiahao Xie, Zebang Shen, Chao Zhang, Hui Qian, and Boyu Wang. Stochastic recursive gradient- based methods for projection-free online learning. arXiv preprint axXiv:1910.09396, 2019.

---

Under review as a conference paper at ICLR 2022
A APPENDIX
It is important that the policy that the boosting algorithm outputs can be evaluated efficiently, To- wards that end, we give the following claim.
Claim 15. For any [N,,,N N, T), x(-ss) for any S can be evaluated using TN base policy evaluations and O(T X (NA+ + Aog A)) arithmetic and logical operations.
Proof. Since E N, it is composed of TN base policies. Producing each aggregated function takes N additions and multiplications: there are T of these. Each projection takes time equivalent to sorting |A] numbers, due to water-filling algorithm (Duchi et al. 2008); these are also in number. The final linear transformation takes an additional TA operations.
B STEP-SIZE SUBROUTINE
Below we give an algorithm for choosing step sizes used in both the RL boosting methods (for online, and supervised, weak learners).
Algorithm StepChooserr(m-uuti P)
1: Execute πe-1 for P episodes with initial state distribution f via Algorithm to get
D {(s P.)
2: For any policy n. - Ep Qi T(-16)).
3: Return
(1-7)²
my clippo.1
G G
C RL BOOSTING VIA WEAK ONLINE LEARNING
Algorithm RL Boosting via Weak Online Learning
1: Initialize a policy To E Iw arbitrarily.
2: for t. = 1 to 7 do
3: Initialize online weak learners Wi... WAN
4: for m 1 to MM do
5: Execute πt-1 once with initial state distribution via Algorithm 2 to get (St.m, @.m))
6: Choose Pt.m, II arbitrarily. for n = to N do
7:
8:
Set Pt.m.n = (1 (t..)). + 92.n ym 12,. (2 - n..
9:
end for
10:
Pass to each 7 the following loss linear ft.m.n:
fum,, -.G.al-Qu.ne (pmm
11:
end for
Declare oi = M
1 EM r [p
13: Choose 7/, min(1, 20 if do else m, StepChooser(mm-1,1/ P).
14: Update Te = (1 m, 7 + 7,
end for
16: Output #= गТ if = do else output T with the smallest T)--
Theorem 16. Algorithu 4 samples T(M + P) episodes of length I- log T(M+P) with probability
1 1- 8. In the episodic model, Algorithm guarantees as long as T 1602 N [6]AA(C.-(1))
(1-7)-E (1-7)"ae
12

---

Under review as a conference paper at ICLR 2022
M = max
2/ (1-7)429a²
log" Tó,
(My (1 Pae
j.H = dg. we have with probability 1
E(TI
-" & (T)
1 1-7 +E
In the v-reset model, Algorithm
guarantees long T
100D 10lAiD Rw(M) aa-
N
20 (1-y)
(1-
P 250D |AI log J. M max ( (11-7)
[0] log b)
(1-
.11
have with
probability 1
- S Doo (11,
(1-7)2 +
If (w(M)
v /M log W| for some measure of weak learning complexity [W], the algorithm episodes in the episodic model, and Ô 12_ 12 ( in the v-
samples Ô
C.2 (M)aaf log WI (1-7)
(11 (1-7))
reset model.
D NON-CONVEX FRANK- WOLFE
this section, we give an abstract high-level procedural template that the previously introduced RL boosters operate in. This is based a variant of the Frank-Wolfe optimization technique, adapted to non-convex and gradient dominated function classes (see Definition D
The Frank-Woll (FW) method assumes oracle access to a black-box linear optimizer, denoted O and utilizes it by iteratively making oracle calls with modified objectives, in order to solve the harder task of convex optimization. Analogously, boosting algorithms often assume oracle access to a "weak" learner, which are utilized by iteratively making oracle calls with modified objective, in order to obtain "strong" learner, with boosted performance. In the RL setting, the objective is in fact non-convex, but exhibits gradient domination. By adapting Frank Wolfe technique to this setting, will in subsequent section obtain guarantees for the algorithms given in Section 4
Setting. Denote by black-box oracle to an (Cg, -ap-oopxx linear optimizer over a con- vex K. C Rdd such that for any given Rdd have
Ovv) Z max co. ueK²
Algorithm 5 Non-convex Frank-Wolfe
1: Input: T' > 0, objective f, linear optimization oracle
2: Choose 2g arbitrarily.
3: for = ,,...,T7
4: Call 2, (V.-1)) where V,-1 (f(++-1)
5: Choose 1/t min 2x in the gradient-dominated case, else choose so that
LD V f1-1)l (---)11))1 s e.
6: Set 2; = (1 2 + 17.22.
7: end for
8: return T= Tr in the gradient-dominated case, else Φ:-1 with the smallest T)-
Theorem 17. f: be L-smooth in some norm || ||.. H --buudded, and the diameter of IC
in ||. be D. Then, for (Co, -linea optimization oracle, the output ă of Algorithm D satisfies
2HLD2
max Vf(z) (1 K
+ 3E + Eg.
T
Furthermore, if T, K2, K2) gradient-dominatel and Ho. ... ET K₁, then it holds
2x² max H
e f(x") f(t) <
max
KeO.
T
13

---

Under review as a conference paper at ICLR 2022
E ANALYSIS FOR BOOSTING WITH SUPERVISED LEARNING (PROOF OF THEOREM
Theorem (Formal version of Theorem Algorithm 7 samples T(MN + P) episodes of length TIMN+PP) with probability 6. the episodic model, Algorithm guarantees as long as
y log 6
16C
N = (6]
2
.M = m (1- (1)]A]
8 NT do. we have with probability
(1-7)"87
(1-7)Pac
8
E(TI,II)
V V & Coo (UI)
+E
1 1-7
In the v-reset model, Algorithm
guarantees as long T
&D2
N
> [1->)
P
200/ log 2T M (1-7)- b
[1 P 8) Dr
2NT , we huve with probability -
(T, 4" < Dx (1->) +E
If 8) log W
log: for some measure of weak learning complexity [W], the algorithm samples episodes in the episodic model, and Ô D LAI log [W]
ò ch (2) log [W
in the v-reset model.
(1-
Proof of Theorem 17 The broad scheme here to utilize an equivalence between Algorithm| Lan
Algorithm Dn the function 5 (or V in the v-reset model), which Theorem 17 applies.
To this end, firstly, note V is - bounded. Define norm |l
IR SIXI||
R as ||
maxses Eae |z Further, observe that for any policy S - A.. | following lemma specifies the smoothness of V in this norm.
The
Lemma 18. V is
27 (1-7)3 -smooth in the || |l norm.
To be able to interpret Algorithm T as an instantiation of the algorithmic template Algorithm D presents, we advance two claims: one, the step-size choices of the two algorithms conincide; two, Th (Line 3-10) serves as approximate linear optimizers for V Together, these imply that the iterates produced by the two algorithms conincide. The first of these, which provides value of to use in the statement of Theorem 17 is established below.
Claim 19. Upon every invocation of StepChooser, the output hh, satisfies with probability
21)11 (1 (1-7)3
(VV m--1) <
16]A
log
11
Next, we move onto the linear optimization equivalence. Indeed, Claim 20 demonstrates that T/ serves a linear optimizer over gradients of the function V the suboptimality specifies eg.
Claim 20. Let B N. and 12.n min 1). Then, for any nद produced by Algorithm
satisfies with probability 8
m() < 2|A
max FEll
VV
+ EW
(1
2a
VN
Finally, observe that it is by construction that E 01. Therefore, in terms of the previous section, AC the class of all policies, K, Π, K₂
In the episodic model, we wish to invoke the second part of Theorem 17 The next lemma establishes dradient-domination properties of 8 to support this.
Lemma 21. V is (T), - Cco (UI) II,, n, I.)) gradient dominated, i.e. for any Ul:
( E(T,, + max (VX ④)
V VE $ (T)
well
14

---

Under review as a conference paper at ICLR 2022
Deriving K, from the above lemma along with cn from Claim 20 and from Claim quence of the second part Theorem 17 we have with probability NT8
19 conse-
- va s (U) ((1, II + (1-7)9T
40 (I)
2]
1 1-
(1-7)PavN N
(1 (1-7)Pa
EW.
Similarly, in the v-reset model, the first part of Theorem] 17 provides local-optimality guarantee for V,_ Lemma 22 provides a bound on the function-value gap (on V") provided such local-optimality conditions.
Lemma 22. For any πT E 01, we have
- V z 1-7
1 _Dxx Doo
(11,
max (V (n' (m/-m)
(
11
1-7
x x'ell
Again, using the bound on max (VVV,) (I' 7) Theorem 17 provides, we have that with probability 2NT8
D (II,II
2Dx
2
48 48/A|D log
V Va
+ tew)
+
7)²
(1 VVv
- a VN
(1 (1-7)3VP
ANALYSIS FOR BOOSTING WITH ONLINE LEARNING (PROOF OF THEOREM 16
we establish an equivalence between Algorithm and AggorithmD the function V (or V in the v-reset model), to which Theorem 17 applies provided smoothness (see Lemma 18
Proof of Theorem Similar the proof of Theorem 11
Indeed, Claim 23 demonstrates T.. serves a linear optimizer over gradients of the function V*, and provides a bound on eg. Claim 19 ensures that that the step size choices (and hence iterates) of the two algorithms coincide. As before, observe that it is by construction that E n.
Claim 23. Let 3 V nN. and m2. min 2, 1}. Then, for any t, Th produced by Algorithm
satisfies with probability 8
VV T/) - 2|A| (1 - 2a
2 VN
(w(MM)
16 16 8-1
max VV
M
M
the episodic model, one may combine the second part of Theorem which provides bound
on fumetion-value gap for gradient dominated functions, which Lemma 21 guarantees, conclude with probability T8
V V S C.. (I))
( (T) 4C3
+ 41A(Coo(1) 2/ (T) Rw(M)
+ 8|A|Coo (T) log 8-1
1-7
(1 (1-7)) 7) (1 (1-
(1 (1-7pa
M
2w
Similarly, in the v-reset model, Lemma 22 provides bound the function-valus gap provided local-optimality conditions, which the first part of Theorem 17 provides for. Again, with probability
1 18
V* v < De,,( 2D.
A
Rw(M)
4 4og d-
A
1 log
+
+
(1 (1-2) (1 - 33
N
M
VM
P
5
15

---

Under review as a conference paper at ICLR 2022
G PROOFS OF SUPPORTING CLAIMS
G. NON-CONVEX FRANK- WOLFR METHOD (THEOREM 17
Proof of Theorem 17 Non-convex case. Note that for any timestep t, it holds due to smoothness
that
[(x)) [(x--1 + ne x(-1))
2 - D2 2 f(1x-1) no Vi-1(20 -I(-1) -1j
(V. (2 (2 x(-1))?
= -[(x-1) 2LD
(LDD (2
2LD
Using the step-size definition to bound on the middle term, and telescoping this inequality function-value differences across successive iterates, we have
2LD H
min(VV -2)))) 1 T Σ (V. 1z (1-1))))) <
2
Let t' arg min, ?r and to arg min, (V/T1 (2t x(-1))² Then
Ve-1(tr - IV- s LD T/ +e S LDd n2- te
2LD²
< Vi--1(z- x1- + + S
V
+ +2
T
To conclude the claim for the non-convex part, observe v + s since ž5' -1) it follows by oracle definition that
Va + vb for a, > 0, and that
max MEA2
V u S Ve-120 + ED.
Pradient-Dominate Case. Define x² arg max f(x) and h4 f(x*)((+=)>)))))")))) - f f(x).
2 h1 S 14-1 7). V 11-1) + 1/1 D2
smoothness
L
< h4-1 T) max 17t v (y x1-1) 1) + 112 D2 17:00
oracle
yEK₂
< 14-1 Th (f(x*) f(xx-1)) + ग - D2
L
nt E0 + I
gradient domination
k
K
Ut 14-1 + 2 4 D2 + (co + k
2
The theorem now follows from the following claim.
Claim 24. Let C' 2 1. Let ge be a H-bounded positive sequence such that
9t S (1 2) 91-1 + of + E.E.
Then choosing o, = min(1, 2C implies gr I 20a max + CE.
G.2 SMOOTHNESS OF VALUE FUNCTION (LEMMA 18
Proof of Lemma 18 Consider any two policies n, n'. Using the Performance Difference Lemma
(Lemma 3.2 in Agarwal et al. 2019), e.g.) and Equation 2 we have
V
V
VV (T² m]
1
EE Eandyr (-sssss) (Tii) (-ls) - x-1ss] - Ex-ar (T (r'(-1s) <-11s)]
5
(1 7)2 || d= 1////|1 π ||o.1
16

---

Under review as a conference paper at ICLR 2022
The last inequality uses the fact that maX,,0 Q (=) I -- It suffices to show I|d" d I 121 T| To establish this, consider the Markov operator pa (s'lss)
Eees S, we have
induced by policy π on MDP M. For any distribution supported on
|1(P"' P=)ddl1
Σ
Σ (o) =(als)
a,
-
Σ P(s' a) F/o00,1 & || π 1loo,,1
Using sub-additivity of the I norm and applying the above observation times, we have for any
[I((P=)) ( ( s 4||x' x x|,,,11-
Finally, observe that
0
||0= d= S (1 11-71 Σ
8 $ || - π b0 -7)
Σ
tr"
|| x1,,0,1
1=0
G.3 STEP-SIZE GUARANTRE (CLAIM T9p
Proof of Claim 19
Let D be the distribution induced by Algorithm 2 upon being given TT-1- Due to Lemma 14 it suffices to demonstrate that for any π E (T/: - the following claim holds with probability The claim in turn follows from Hoeffding's inequality, while noting Q (s,
is bounded in the loo norm.
|A|
8|A1|
E
(e. (1.0"t-i(e:))))
Qu- (s, (a(.)))(()s))
log
(1 v)v
28
G.4 GRADIENT DOMINATION (LEMMA 21 AND LEMMA 22
Proof of Lemma
21
Invoking Lemma 4.1 from Aggaraal al. 2019) with μ = do, we have
d
V
<
max(VVT) (m - T)
d
RC
<
Coc
(max((VVV) T Tp max VV") n'' + max VV") (T' VV=)T(T'' - =)))
*'ell
w'ell
Finally, with the aid of Equation observe that
max (VV") T my
max x'ell
(V x'
min *'ell 1 Exad
- max a) m|
40
1 E(II
Proof of Lemma 22
Invoking Lemma 4.1 from Agarwal et al. 2019 with μ = we have
V+ v
<
max max(VV.)) VV
(To - T)
1
1/
no
1
<
Doo (max VV
To
max VV r'ell
max VVA) V (T)-
1
z'ell
17

---

Under review as a conference paper at ICLR 2022
Again, with the aid of Equation
observe that
max
(Vax)VVV7)
max ( VV,
min x'ell 1
E Bawdy
max Q" - Q-((s) (1(1)
T1
1 1-9 (TI
G.5 SUPERVISED LINEAR OPTIMIZATION GUARANTEES (CLAIM 20
Proof of Claim 20 The subroutine presented in lines 3-10 (which culminate in mT) is an instantiation of Algorithm from (Hazan & Singh| 2021). specializing the decision set to be A To note the equivalence, note that in (Hazan & Singh| (222)) the algorithm is stated assuming that the center-of- mass of the decision set the origin (after a coordinate transform); correspondingly, the update
rule in Algorithm can be written
(pt, (1- (1- Tr) 12.n (Ar,a Ty)-
For any state s, (T(sss 11.11 corresponds to the center-of-masee masss of A Finally, note that maximizing, f over K. is equivalent minimizing (-f) x over the same domain. Therefore, we can borrow the following result on boosting for statistical learning from (Hazan & Singh 2021)
AA (Theorem 13). Note that Q=(ss)) produced by Algorithm 2 satisfies [|Q T-7- Let Dj be the distribution induced by the trajectory sampler in round T.
Theorem 25 ((Hazan& & Singh 2021 Let B = v aN. and f2.n min [ 2 1}. Then, for any at.
produced by A Algorithm 7 satisfies with probability 1 - 8 that
2|A1
2
max ( Q), [QTT(x [(s] ((..))D. [QT [{) (1-
+8
well
Lemma 14 allows to restate the guarantees the previous subsection terms of linear optimiza- tion over functional gradients. The conclusion thus follows immediately by combining Lemma [4]
and Theorem 25
G.6 ONLINE LINEAR OPTIMIZATION GUARANTEES (CLAIM) 23
Proof of Claim 23 In a similar vein to the proof of Claim 20 here we state the a result on boosting for online convex optimization (OCO) from (Hazan Singh 2021 (Theorem 6), the counterpart of Theorem 13 for the online weak learning case.
Theorem 26 ((Hazan & Singh 2021 ). Let V aN. and man min 2 1}. Then, for any t,
[(prm,,)) produced by Algorithm satisfies
M
[T. ((tmm)
M
@n N(Pm...((sm.)))
< 2|A|
22M
+ Rwv(M)
max WELL
(1 - 71- VN
m=11
Next we invoke aaline-to-bateh conversions. Note that in Algorithm (St.m- QL.)) for any fixed t is sampled i.i.d. from the same distribution. Therefore, apply online-to-bate results, i.c. Theorem 9.5 in (Hazan 2019) on Theorem 26 to get
2|
2
Rw(M)
16 log 8
max (DQ)DD [Q - [QT [s(s
+
+
7)0
VN
M
M
We finally invoke Lemma
18

---

Under review as a conference paper at ICLR 2022
G.7
REMAINING PROOFS (CLAIM 24
Proof of Claim 24 Let T = arg max < 2C). For any S T*, we have or = 1 and
9t S H
S
2 Fort t T", we proceed by induction. The base case (t T*) is true by the F
previous display. Now, assume -c-1 I 20 max
CE for some t T"
91 - 1 2 ?-
2C max (2D, max H)
4C
2CE
+ CE
+
t-1
1
$ CE + 2C max(2D. H}
+ 82
t- 1
t²
2f +
-C= [2D, II|
(2(1-1)
t(t 1)
$ CE 2C max (2D, H)
f(t- 1)
19


Reviews:
[{"review_id": "lbme5TvtJDh", "reviewer": "Reviewer_Zawz", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "FYI: this is an emergency review that I agreed to do earlier today, so I have not examined the appendix in detail.\n\nThe paper is extremely dense and hard to read in many places. It suffers substantially from notation overload. It is very hard to parse the results and contributions since they are obscured by very dense notation. This is further made difficult by a few typos and undefined notation in some places. The paper reads like a list of mathematical concepts / definitions that are not really strung together in a coherent (to the reader) manner. I have no doubt that these concepts are all important to the results, but the paper would be vastly improved by a) improving clarity and doing more to help guide the reader's understanding of what is going on and why it is important and b) reducing the notation significantly, even at the loss of some generality or at the expense of moving some material to the appendix.\n\nThis paper would also be improved significantly by a numerical example, even on something very simple like a grid world. I was left with no intuition about how this method would perform in practice. In a similar vein, the paper did not discuss when / if one should use the main proposed algorithm. At the start the authors mention working in 'very large MDPs' and 'MDPs with large state space' - but that is not really supported with any discussion or experiment (other than the complexity bound, which is not enough to build intuition).\n\nThe 'two-layer neural network' is mentioned a few times, but I don't really see how it is used / discussed. Where in the algorithm is the two layer NN used?\n\nNot enough discussion is given to the basics of boosting.\n\nI like the inclusion of the proof sketch, but it should be even more detailed and should provide much more intuition.\n\nSeveral claims are made in the paper without citation - eg the sentence \"Training deep neural networks in the supervised learning model is known to be computationally hard\". This requires citations not just because it is a controversial claim, but because you say it is 'known' but you don't provide the reader with a way to learn about it if they are unaware of this fact. This pattern is repeated in several places, eg: \"However, in general no learner can outperform a random learner over all label distributions (this is called the “no free lunch\" theorem).\" Please give the reader a reference to learn about this theorem.\n\nA big benefit of the proposed algorithm is that the final complexity bound does not depend on the number of states, which is a very interesting result. However, I have no idea how that came about. The paper should explain how the authors managed to get rid of the dependence on S.\n\nOne point I am confused about - \"assume the availability of an efficient exploration scheme\" - where / how is this assumption used?\n\nThe paper says: \"we assumes access to a weak learner: an efficient sample-based procedure that is capable of generating an approximate solution to any linear optimization objective over the space of policies\" but also says that the problem over policies is non-convex (ie, non-linear). Do you mean to say 'linear optimization objective over the space of **state-visitation distributions**'?\n\nMinor points and typos:\n\n* 'w.r.t.' - don't abbreviate\n* \"we assumes\"\n* \"weak learner that attains\"\n* Is the initial state distribution mu or d0?\n* Page 4 - What is d_d ? Is s_0 \\sim d_0 or d ? \n* I do not understand the equation in Definition 2 at all\n* \"always slight better\"\n* What is d \\mu in Assumption 1? What is D(s, l).\n* What is R_W(M) in Definition 7?\n* \"weak learning is provided\"\n* bellman -> Bellman\n* Several terms in Alg 1 are undefined (eg. \\eta_2 never defined, \\hat Q never defined). The period is misplaced after line 6.\n* Theorem 11:  \"Algorithm 1 samples T(MN + P) episodes of length O˜(1/1−γ) with probability 1 − δ.\" I do not understand what 1-\\delta is doing there.\n* \"Note that Qπ (s, ·) produced by Algorithm 2 satisfies ||Qπ (s, ·)|| =|A|\\1−γ.\" What norm is this? Where is that justified?\n\n\n", "summary_of_the_paper": "The paper proposes boosting (using Frank-Wolfe) weak RL learners to get a strong (in a concrete sense) policy. The main theoretical bound does not depend on the number of states, which indicates that the method should be competitive in very large state-space MDPs.", "summary_of_the_review": "An interesting result, however I cannot recommend publication due to significant clarity and readability issues.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "dTWwnCWgey9", "reviewer": "Reviewer_Kp4W", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength\n\n1. This paper studies boosting methods in RL, which is an interesting topic on its own and has not been explored much from the theoretical perspective yet.\n2. The algorithm uses a variant of the Frank-Wolfe method to overcome the non-convexity of the value function (with respect to the policy space). To do so, the analysis relies on recent investigation of the policy gradient algorithm which identify conditions under which the value function is gradient dominated. The application of  the Frank-Wolfe method in RL seems interesting. \n3. The writing of the paper is well-structured and very easy to follow. The analysis looks rigorous. \n\n\nWeakness:\n1. The authors only consider weak learner that optimizes a linear function over policy space, which seems restrictive. \n2. The analysis does not look very novel given prior work (Hazan & Singh, 2021). ", "summary_of_the_paper": "In this paper, the authors study boosting in RL, i.e., how to convert weak learners into effective policies. The authors provide an algorithm that improves the accuracy of the weak learners iteratively, and the sample complexity and running time do not explicitly depend on the number of states. \n\nIn order to overcome the non-convexity of the value function (with respect to the policy space), the authors use a non-convex variant of the Frank-Wolfe method together with recent advances in gradient boosting. ", "summary_of_the_review": "Weighing the strength and weakness of the paper, I am recommending weak accept.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "WNEKfuqEOR", "reviewer": "Reviewer_8LJa", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths\n\n- The authors propose an interesting and novel approach to solving the RL problem with unknown transition function and large state space. The use of combining weak learners and leveraging boosting ideas from supervised learning seems significant and new. I believe the core idea will be valuable to both RL and optimization communities.\n- The proposed algorithm aims to be agnostic, offering a way to bypass common structural assumptions (e.g. linearity) as long as one has access to certain weak learners. Such a setting has not been explored much previously in RL theory to my knowledge.\n- The technical results needed to achieve the sample complexity guarantee may be of independent interest.\n- The proofs seem reasonable, but I did not carefully check.\n\n\nWeaknesses\n\n- I think an example of a valid weak learner that satisfies either the SL or online assumptions would be very helpful for understanding the applicability of the results. For instance, are there existing algorithms that could generate such weak learners easily? Perhaps the answer is obvious, but in any case this seems like an important missing piece.\n\n\n- The paper is very tersely written and not easy to understand. There is little motivation or justification for both definitions and algorithmic/analytical design choices. Many are simply stated. Even some theorems (11, 13) are just stated. I believe a remark or an interpretation or a comparison with prior work would be enormously helpful. There is no description of any steps in Algorithm 1 besides the algorithm box itself. This issue is also compounded by the fact that there are many notational inaccuracies (see minor comments below for a subset), so a reader trying to parse the approach and results cannot reliably just read the math either.\n\n\nSpecific examples of lack of motivation of *definitions*: “The extension operator… operate overs functions and modifies their value…” Why are we interested in such an operator? Are there other operators we could use in its place? \n“To state the results, we need the following definitions” Why do we need these definitions? Are they being used to sweep certain problems under the rug (i.e. Def 10 for exploration)?\n\nI believe these parts (and others throughout) would significantly benefit from more supporting text explaining the reasoning. \n\n\nMinor comments:\n- It would be helpful to also include more discussion about the known achievable PAC sample complexities for RL and MDPs in the tabular case in order to highlight the difference with the state-space independent results here. For example, generative models (not the same setting but close): “Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal” (Agarwal et al, 2019)\n- Assumption 1 seems strong since it looks like the weak learner is required to be good on any potential distribution induced by the policies. Can you elaborate on this? An example, as suggested earlier, would be helpful.\n- R_W is never defined in the main text.\n- $\\eta_{2, t}$ is undefined in Alg 1 until Thm 13.\n- The input parameters of Alg 1 are not described. One has to look at Alg 3 in the appendix to see what P is even used for.\n- M and P are overloaded.\n- In the definition of M in Theorem 11, there is a little m followed by a tuple. What is this?\n- Little m is undefined in Alg 1.\n- Thm 11: $\\pi$ is undefined. I think this should say $\\bar{\\pi}$.\n- Thm 11 (and elsewhere): From what I can see, the policy class $\\Pi$ is never defined except in some places it is said to be an arbitrary base subset of all policies. When used in the theorem, is this meant to be $\\Pi_W$? How should we interpret the term involving $\\mathcal{E}$ in Thm 11 (depending on the answer to the previous question)?\n- There is no Alg D. I think this should be Alg 5.\n\n", "summary_of_the_paper": "This paper proposes a new approach for solving RL problems with sample complexity independent of the number of states. Rather than imposing structural assumptions, the authors consider access to weak learners and propose a way to combine these weak learners effectively to generate a near optimal policy. The sample complexity result is competitive and does not depend on the number of states, under the assumption of access to weak learners.", "summary_of_the_review": "I believe the results are interesting, decently significant, and relevant to the community. That being said, there are issues with clarity (noted above). I believe fixing these issues is an easy way to significantly strengthen the paper.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "Oq7jQ7oUsh", "reviewer": "Reviewer_LN8M", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n1. The idea of transferring the most recent online boosting technique to RL is interesting. \n2. This paper gives solid theoretical analysis of the proposed algorithms.\n\nWeakness:\n1. The novelty looks limited as the techniques are very similar to Hazan and Singh 2021. Moreover, this paper does not discuss the major difficulty of designing boosted RL compared to designing boosted contextual bandits, which has already been proposed in existing literature.\n2. The presentation has some problems. If this paper aims to deal with the large state space problem in RL, then it misses some important related work in state compression techniques.\n3. Although this paper is mainly theoretical, some initial experiments will be beneficial to validate the effectiveness of the proposed algorithms. Hazan and Singh 2021 also gives some experiments.", "summary_of_the_paper": "This paper studies boosting-like RL algorithms using the most boosting techniques from online learning. It advocates the advantage of the proposed algorithm as the sample complexity's independence of the number of states. ", "summary_of_the_review": "This paper extends the recent online boosting technique to the RL setting. The current presentation has some problems and the technical novelty looks a little bit incremental.\n\nI recommend the authors to (1) discuss the difference between designing boosted contextual bandits and boosted RL; \n(2) design some initial experiments to justify the effectiveness of the proposed algorithms. \n(3) consider to present the logic of this paper in another way (not motivated by the large state problem in RL). ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "4wKjyq8M74I", "reviewer": "Reviewer_aFPg", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I was called to do an urgent review on this submission and I did not have time to check the mathematical details in full. \nIn general I do not think the paper is well-written, as many notations are directly referred to without definition such as \\mathbb{\\Lambda}, \\mathbb{\\Pi}, d_0, d_{d_0}, d^{\\pi}, R_{\\mathcal{W}}(M). \nIt is difficult to catch the main idea of this paper, and it is dubious if the proposed algorithm can be implemented in practice. Specifically, \n- how should one compute $\\nabla F_{G,\\beta}$ in practice? \n- How does one know that a function $f$ which satisfies the definition 2 (function aggregation) exists? How does one know that a policy $\\lambda$ that satisfies the definition 4 (shrub) exists?\n- In practice, is there a way to estimate policy completeness as defined in Definition 9?\n- In definition 10 (distribution mismatch), is there any assumption made to ensure that $C_\\infty \\ne \\infty$?\n- Any explicit comparison between the proposed boosting-enhanced learning algorithms and no-boosting RL learning algorithms?\n\nThe meaning of notations is inconsistent from place to place. \n- $P$ in theorem 11?", "summary_of_the_paper": "This paper attempts to deploy the boosting technique in the supervised learning on policy learning in the RL setting. The author suggests a protocol to do policy aggregation from weak policies through the quantity $\\textit{the extension operator}$, and presents the probabilistic convergence guarantee for the learning process.", "summary_of_the_review": "I suggest the paper be added more clarification of notations and interpretation of main results. The paper is certainly not ready to be published due to its lack of clarity and unrefined narrative.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a boosting algorithm for RL based on online boosting. The main advantage of the result is that the sample complexity does not explicitly depend on number of states. Post rebuttal, some of the reviewers have changed their opinion on the paper. However, overall the reviewers still seem to be on the fence about this paper. Seems like the paper combines the techniques from Hazan Singh’21 along with a frank-wolfe algorithm to deal with non-convex sets but the reviewers seem to view this as not as significant a new contribution. 

I see the paper as being interesting but do agree with some of the comments of the reviewers and am leaning to a reject.
Decision: Reject