A Boosting Approach to Reinforcement Learning
Authors: Nataly Brukhim
Elad Hazan
Karan Singh
Venue: NeurIPS 2022 Accept (2022)
Keywords: boosting
reinforcement learning
non-convex Frank-Wolfe

Abstract: Reducing reinforcement learning to supervised learning is a well-studied and effective approach that leverages the benefits of compact function approximation to deal with large-scale Markov decision processes. Independently, the boosting methodology (e.g. AdaBoost) has proven to be indispensable in designing efficient and accurate classification algorithms by combining rough and inaccurate rules-of-thumb.

In this paper, we take a further step: we reduce reinforcement learning to a sequence of weak learning problems. Since weak learners perform only marginally better than random guesses, such subroutines constitute a weaker assumption than the availability of an accurate supervised learning oracle. We prove that the sample complexity and running time bounds of the proposed method do not explicitly depend on the number of states.

While existing results on boosting operate on convex losses, the value function over policies is non-convex. We show how to use a non-convex variant of the Frank-Wolfe method for boosting, that additionally improves upon the known sample complexity and running time bounds even for reductions to supervised learning.

A Boosting Approach to Reinforcement Learning
Nataly Brukhim Princeton University nbrukhim@cs princeton.edu serukhimdss.princeeon..e
Elad Hazan
Princeton University
Google AI Princeton
ehazan@cs. wrw.ecssppiiinetee wwwppritonnnneeememmm edu
Karan Singh Carnegie Mellon University karansingh@cmu. edu
Abstract
Reducing reinforcement learning to supervised learning well-studied and effective approach that leverages the benefits of compact function approximation to deal with large-scale Markov decision processes. Independently, the boosting methodology (e.g. AdaBoost) has proven to be indispensable in designing efficient and accurate classification algorithms by combining inaccurate rules-of-thuml
In this paper, we take a further step: we reduce reinforcement learning to a sequence of weak learning problems. Since weak learners perform only marginally better than random guesses, such subroutines constitute weaker assumption than the availability of accurate supervised learning oracle. We prove that the sample complexity and running time bounds of the proposed method do not explicitly depend on the number of states.
While existing results on boosting operate on convex losses, the value function over policies is non-convex. We show how to use a non non-convex variant of the Frank-Wolfe method for boosting, that additionally improves upon the known sample complexity and running time even for reductions to supervised learning.
Introduction
In reinforcement learning, Markov decision processes (MDP) model the mechanism of learning from rewards, opposed examples. Although the case of tabular MDPs well understood. the main challenge in applying RL in the real-world is the size of the state space in practical domains.
This challenge of finding efficient and provable algorithms for MDPs with large state space is the focus of our study. Various techniques have been suggested and applied to cope with very large MDPs. One class of approaches attempts approximate either the value or the transition function of the underlying MDP by using parametric function class. Such approaches invariably make strong realizability assumptions produce global optimality guarantees. Another class of approaches, so-called direct methods, produces a near-optimal policy that maximizes the expected return from a given policy class. To deal with the challenge of large (possibly innumerable) policy classes, popular strategy [24] is to the frame policy search as a sequence of supervised learning problems. Such approaches yield global optimality guarantees under state coverage assumptions without reliance on realizability, and have inspired practical adaptations for sampling-bas bbsed policy search.
In this paper, study another methodology derive provable algorithms for reinforcement learning: ensemble methods for aggregating weak or approximate algorithms into substantially more accurate solutions. Our proposal extends the methodology of boosting, typically used to solve supervised learning instances [32], to reinforcement learning. A typical boosting algorithm (e.g. AdaBoost)
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Supervised weak learner
Online weak learner
Episodic model
1/ate5
1/a2
Rollouts w. v-ressts
1/a*c6
1/a2
Table 1: Sample complexity of the proposed algorithms for different a-weak learning models (supervised & online) and modes of accessing the MDP (rollouts & rollouts with reset distribution v), terms of e and a, suppressing other terms. This work the first introduce a reduction of RL to weak supervised learning. See Theorem 7 for details.
Supervised strong learner
This work (Corollary
CPI
24
Episodic model
1/ea
1/E*
Rollouts w. v-resets
1/e
1/64
Table 2: Compared to previous work 24),, the table shows sample complexity of the proposed algorithm for strong (a 1) supervised learning model and different modes of accessing the MDP.
iteratively constructs a near-optimal classifier by combining computationally cheap, yet inaccurate rules--ffthhmb. Unlike RL reductions to supervised learning which assume the existence of an efficient and accurate classification or regression procedure, the proposed algorithms builds on learning algorithms that perform only ever-so-slightly better than random guess, and which thus may be produced cheaply both in computational and statistical terms.
Concretely, we assume access to weak learner: an efficient sample- based procedure that is capable of generating an approximate solution to any weighted multi-class objective over fixed policy class, We describe an algorithm that iteratively calls this procedure carefully constructed new objectives, and aggregates the solution into a single policy. prove that after sufficiently many iterations, our resulting policy has competitive global gurantees performannce. Interestingly, unlike boosting algorithms for regression and classification, our resulting aggregation weak learners is non-linear.
1.1 Challenges and techniques
Reinforcement learning is quite different from supervised learning and several difficulties have to be circumvented for boosting to work. Among the challenges that the reinforcement learning setting presents, consider the following.
(a) The value function not a convex or concave function of the policy. This is true even the tabular case, and even more so if we use 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 can only be computed approximately.
(c) It is unrealistic to expect a weak learner that attains near-optimal value for a given linear objective over the policy class. At most one 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 of the value function, we use novel variant of the Frank- Wolfe optimization algorithm that simultaneously delivers on two guarantees. First, finds a first order stationary point with near-optimal rate. Secondly, if the objective happens to admit certain gradient domination property, an important generalization of convexity, also guarantees near optimal value. The application of the nonconvex Frank-Wolft method is justified due to previous recent investigation of the policy gradient algorithm 2 1. which identified conditions under which the value function is gradient dominated.

---

The second ceermaationtthooreie challenge of the unknown transition function is overcome by careful algorithmic design: our boosting algorithm requires only samples of the transitions and rewards. obtained by rollouts on the MDP.
The third challenge is perhaps the most difficult overcome. Thus far, the of the Frank-Woll method in reinforcement learning did not include a multiplicative approximation, which is critical for our application. We adapt the techniques used for boosting in online convex optimization [99] with a multiplicative weak learner to our setting, by non-linearly aggregating (using a 2-layer network) the weak learners. This aspect perhaps of general interest to boosting algorithm design, which mostly based on linear aggregation.
1.2 Our contributions
Our main contribution is a novel efficient boosting algorithm for reinforcement learning. Our techniques apply in various settings and the sample complexity bounds of all of our results are summarized in Tables [and] 2
The input to this algorithm is weak learning method capable of approximately solving weighted multi-class problem instance over a certain policy class. The output of the algorithm is a policy which does not belong to the original class considered, hence being an instance of improper learning. It is rather a non-linear aggregation of policies from the original class, according to a two-layer neural network. This result of the two-tier structure of our algorithm: an outer loop of non-convex Frank-Wolt Wolfe method, and an inner loop of online convex optimization based boosting. The final policy comes with provable global optimality guarantees.
Beyond novelty of techniques, an important contribution (Table IT of our work is to highlight the quantitative difference in guarantees that depend the mode of accessing the MDP (episodic rollouts vs. access to an exploratory reset distrbution) and the nature of the weak learners (online vs statistical), thus indicating that some algorithmic choices may be preferable compared to others in terms of speed of convergence and sample complexity.
As with existing reductions to supervised learning [24]. these global convergence guarantees happen under appropriate state coverage assumptions either via access to a reset distribution that has some overlap with the state distribution of the optimal policy, or by constraining the policy class to policies that explore sufficiently. Yet another contribution of our work is to show an improved sample complexity result in the latter setting, even when considering reductions to supervised learning instances. This improvement in convergence in well-studied settings is documented in Table 2
1.3 Related work
Reinforcement learning approaches for dealing with large-scale MDPs rely on function approximation [35 Such function approximation may be performed on the underlying conditional probability of transition (c.g. [3| (11) or the value function (c.g. (6). The provable guarantees in such methods come at the cost of strong realizability assumptions. In contrast, the so-called direct approaches attempt policy search over an appropriate policy class (2) I. and rely on making making incremental updates, such variants of Conservative Policy Iteration (CPI) [4 33 4] and Policy Search by Dynamic Programming (). These provide convergence guarantees under appropriate state coverage assumptions comparable ones made in this work.
Our boosting approach for provable RL builds on the vast literature of boosting for supervised learning (2. and recently online learning [27 12
One of the crucial techniques important for our application is the extension of boosting to the online convex optimization setting, with bandit information [10), and critically with multiplicative weak learner [19.. This latter technique implies a non-linear aggregation of the weak learners. Non-linear boosting was only recently investigated in [5]. where it was shown to potentially enable significantly more efficient boosting. Another work on boosting in the context of control of dynamical systems B. However, this work critically requires knowledge of the underlying dynamics (transitions) and makes convexity assumptions, which we do not, and cannot cope with a multiplicative approximate weak learner.
13 7
22 23
the context of classification
The Frank-Wolfe algorithm is extensively used in machine learning, see e.g. (20), references therein, and recent progress in stochastic Frank-Wolfe methods [16 28 39.. Recent literature has applied variant of this algorithm to reinforcement learning in the context of state space exploration [18]
3

---

2 Preliminaries
Optimization. We say that a differentiable function f K. + R over some domain K C Rd is L-smooth with respect to some norm || if for every I,y E K we have (s()) f(x) Vf(x) (y =)] < | vll?. We define the projection I RIAI + AA. with respect to a set A, where AA denotes the probability simplex over A. For any x RRA,, [[ arg yE || - yll An important generalization of the property of convexity we use henceforth is that of gradient domination.
Definition 1 (Gradient Domination). A function f A - R is said to be K2), gradient dominated (around K, by K2) if for all æ E Kr, it holds that
max f(v) f(z) I K max VVf()) x]} +T. yEA
yEKa
Markov decision process. An infinite-horizon discounted Markov Decision Process (MDP) M = (S, A, P,r,, P,r,,,, do) is specified by: state space S, an action space A, transition model P where P(s'|s, a) denotes the probability of immediately transitioning to state s' upon taking action a at state reward function S x A - [0, where r(s, a) is the immediate reward associated with taking action a at state 8, a discount factor E [0. 1); starting state distribution do over S. For any infinite-length state-action sequence (hereafter, called trajectory),
assign the following value V(s = (#n, an, ,1,01..... )) Li=p (r((s,, (st,,,,). az). The agent interacts with the MDP through the choice of stochastic policy π S An it executes. The execution of such policy induces distribution over trajectories = (so, .o....) as P<<(T) do(so) I (((4411 (s, ae ) (aals))) Using this description we can associate state (*(s) and state-action Q" (s,a) a) value function with any policy т. For an arbitrary distribution d over S, define:
(s) = E
r'r(si at) n,, 80 = 8, =
t=
( [Q" (s, a) s), V2 E | [s)(T)]
Here the expectation is with respect to the randomness of the trajectory induced by æ in M. When convenient, we shall use V to denote Vž,- and V to denote max, V*
Similarly, to any policy n, one may ascribe (discounted) state-visitation distribution d= =
D
(1))
Σ CiS,
P(s ~ d)
t=0
Modes of Accessing the MDP. We henceforth consider two modes of accessing the MDP, that are 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 v-restarts. This is similar to the episodic setting, but here the agent may draw from the MDP a trajectory seeded with an initial state distribution j dg- This interaction model was considered in prior work on policy optimization [24] 2) The motivation for this model is two-fold: first, v can be used to incorporate priors (or domain knowledge) about the state coverage of the optimal policy; second, provides mechanism to incorporate exploration into policy optimization procedures.
2.1 Weak learning
Our boosting algorithms henceforth call upon weak learners generate weak policies. We formalize the notion of a weak learner next. We consider two types of weak leamers, and give different end results based on the different assumptions: weak supervised and weak online learners. In the discussion below, let и Rand be uniformly random policy, i.e. V(s E Sxx A, Ra]ns(])s) = 1/|4|. The formal definition and results for the online setting are deferred to the appendix. In what follows define the supervised weak learning model.

---

The natural way to define weak learning is an algorithm whose performance 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 random learner over all label distributions. This motivates the literature on agnostic boosting 25 g 19 that defines a weak learner as one that can approximate the best policy in a given policy class.
Definition (Weak Supervised Learner). Let a E (0, 1]. Consider a class L of linear loss functions RA + R, family D of distributions that are supported over S x L. and policy class II. A weak supervised learning algorithm, for every E, > 0, given m(e, 5) log [wl log 5 samples Dm from any distribution D E D outputs a policy W(Dm) m) ) E II such that with probability 1 1-8, 8,
(is.))-D(e(W(D)
& a min ((,))) [[(TT [((T(((())) (s)) + (1 - a) (s))) [(TRaa)())) + x x'ell
Note that the weak learner outputs policy in II 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. Specifically, we define a class of natural distributions ID, such that DD E ID if and only if there exists some π E [1] such that, D(s) = Sg D(s, ()du(() d= (s). In particular, while natural distribution may have arbitrary distribution over labels, its marginal distribution over states must be realizable as the state distribution of some policy of weak learning adapts to the complexity of the MDP itself. As an extreme example, in stochastic contextual bandits where policies do not 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 dg.
over the MDP M. Therefore, the complexity
3 Algorithm & Main Results
In this section we describe our RL 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.
3.1 Policy aggregation
For a base class of policies II, 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. That is, our approach
be thought of as aggregation of base policies, which forms 2-layer neural network, as depicted in Figure 1 The leaves of the tree are the policies π E II the base policy class. These are then linearly aggregated form the first layer of the tree, denoted #1 72 in Figure D
Next, each linear combination of policies in the overall aggregation undergoes a projection operation. The projection may be viewed non-linear activation function, such ReLU, in deep learning terms. Note that the projection of any function from S to IR Al produces policy, i.e. a mapping from states to distributions over actions. In the analysis of our algorithm we give a particular projection operation I'[-] which allows us to yield the desired guarantees.
['[m]] to be Definition 3 (Policy Projection). Given म. S + |R, define a projected policy policy such that simultaneously for all s E S, holds that T (-|ss) = [T])]
Definition 4 (Policy Tree). A Policy Tree N C S - A with respect to IT C S An some base policy class, and N, T E N, is a linear combination of projected policies I [it). where each स is linear combination of N base policies x E 11.
This final definition describes the set of possible outputs of the boosting procedure. It is important that the policy that the boosting algorithm outputs can be evaluated efficiently. In the appendix show it is indeed the case (see Lemma 12p. Hereafter, we refer to a Policy Tree with respect to II, N and T, as U1 for N,T T Oppoly( (IA), (1 7) ,e a log 8 d-1)) specified later.
3.2 Main results
Next, we give the main results of our RL boosting algorithm via weak supervised learning, specified in Algorithm I
5

---

A Policy Tree .
[
72
Figure 1: The figure illustrates a Policy Tree hierarchy (see Definition output of the boosting procedure specified in Algorithm [1 Specifically, it is obtained by setting on the inner loop of Internal Boost (Al (Algorithm 2). and 7 = 2 on the main booster (Algorithm 1. Overall we get all base policies T1,-.. Te on lower level, form the Policy Tree In.
Algorithm RL Boosting
1: Input: number of iterations T, initial state distribution μe, and P. N.N M parameters for Internal Boost.
2: Initialize a policy To E Il arbitrarily.
3: for t = 1 to T do
4: Run Internal Boost (Algorithm{2) 2 with distribution ju and policy n, to obtain ny.
5: Update गे (1 1/ 7/
6: end for
7: Run each policy n. for P rollouts compute an empirical estimate V of the expected return.
8: return = N.. where t' arg max, V
To state the results, we need the following definitions. The first generalizes the policy completeness notion from 333. It may be seen the policy-equvvaeent analogue of inherent bellman error [29). Intuitively, it measures the degree which a policy II can best approximate the bellman operator in an average sense with respect to the state distribution induced by policy from [].
Definition 5 (Policy Completeness). For any initial state distribution μ., and policy classes II, D. define E = max=en min E,-dy [max.e Q (s. Q" (s.-) r-[ss]
Definition (Distribution Mismatch), Let n" = arg max, V", and v a fixed initial state dis- tribution (see section 2). Define the following distribution mismatch coefficients: Cx max dd /d D = =|ddd ///l
The above notion of the distribution mismatch coefficient often useful to characterize the exploration problem faced by policy optimization algorithms. We now give the main result for the output of our RL boosting algorithm, assuming supervised weak learners.
Theorem 7. Algorithm I samples T(MN + P) episodes of length Ö Ö(1L))
with probability 1 - 8.
In the episodic model, with μ do. for tht min(1, 2xx }. T = 0 (1-)
16l (1-7))ar
M =
(o Cxl NT with probability 5, V V S
Cock I-7
+
In the v-reset model, with p v, for nh
8 8イ(1~))
T
8D2
N
16 16/ (1-7)
APT
(1-7)8as M m [BA|D ZRTT, with probability 8, V*- V
D=
<
(1-7)²
+
Sample complexities: If (( Ing [W] log 1 for some measure of weak learning complexity (W].

---

Algorithm 2 Internal Boost
1: Input: number of iterations N, number of episodes M, initial policy initial state distribution
μ..
2: Set it to be arbitrary policy in II.
3: for n n= 1 to N do
4: Execute with via Algorithm 3 for . episodes, to get D, {(s;. 20 - such that for all i [ma]:
5: Modify Dn to produce a new dataset D/2 {(s, fi)).
| (-1s;) 211
(y: (-(())))),
y1 arg min Q7 y + G min ||=- yll +
VER
SEAA
2/
where G = --,,, (1-7}3 and fi, Q E RIAI
6: Let An be the policy chosen by the weak learning oracle when given data Dr p,n-
7: Update
an (1 12, ) n-
72.0 An
a
8: end for
9: return I [
Algorithm 3 Trajectory Sampler: samples state ~ d", and an unbiased estimate of Q"
1:
Sample state 8g ~ μ., action a' ~ ((A) uniformly.
2: Sample ~ dl as follows: every timestep h, with probability 7 act according else, accept 9₁, as the sample and proceed to Step
3: Take action a' at state 84, then continue execute and use termination probability of y- Upon termination, set R(sh, a') as the undiscounted sum rewards from time h onwards.
4: Define the vector Q such that for all A, Q7, (a) |A| R(sh, a') -a=aa-
5: return (8h, Q
the algorithm samples ò Co (A]l log W in the v-reset model.
episodes in the episodic model, and Ô
[D_ 122.1 LAI log [W] ( (1-7)180'3
[1-7)"
Theorem 7 above pertains to the case where a weak learning algorithm is available. However, another main result is given by considering the simpler approach of reduction of RL to a strong supervised learning algorithm. In particular, when running our main boosting algorithm, we can replace the call to Internal Boost (in Line 4 of Algorithm [ with a call to a strong supervised learning algorithm. By a similar analysis to that of Theorem 7 we obtain the following corollary.
Corollary 8. Let mlc. 5) log [Wl log 5 for some measure of weak learning complexity [W], When run with a supervised learning oracle ODefinitionnwii Algorithm samples ò G2 log (WI) episodes in the episodic model, and Ô D log (W)) in the
e²
1, i.e. N 1) as the Internal boosting,
v-reset model, to guarantee V V S CocE + with probability 1 in the episodic model and D= in the v-reset model.
1-y
V - V
(I-7)²
We note that this result is an improvement over previous results in terms of sample complexity requirement of the algorithm. In particular, in [24]. Theorem 4.4 and Corollary 4.5 achieve the same guarantee using O(1/e*) samples regardless of the MDP access model. Briefly, CPI utilizes 1/E² calls to an c-optimal supervised learning oracle (each call needing 1/e² samples) to reach e-local optima of the value function. Under requisite state coverage assumptions, this translates to e-function value suboptimality. Indeed, such mode of analysis via first arguing for convergence to local optima for the CPI algorithm can shown be tight. The improvement in our case for the episodic access model comes from the insight that it is possible to make direct claims on the function value sub-optimality (second part of Theorem bypassing the need for making a claim on the local optimality, in the gradient-domee gradient-dominated case.
7

---

3.3 Trajectory sampler
In Algorithm we describe an episodic sampling procedure, that is used in our sample-based RL boosting algorithms described above. For a fixed initial state distribution ls, and any given policy T, we apply the following sampling procedure: start at an initial state 80 ~ 14, and continue to act 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 QT (s, -); see Algorithm 3 for the detailed process.
Sketch of the analysis
Non-convex Frank- We give an abstract high-level procedural template that the previously
introduced RL boosters operate in. This is based on a variant of the Frank-Wolfe optimization technique [13], adapted non-convex and gradient dominated function classes (see Definition M (FW) method assumes oracle access to black-box linear optimizer. denoted O
The Frank-Waon and utilizes by iteratively making oracle calls with modified objectives, in order to solve the harder task of convex optimization. Analogously, boosting algorithms often assumee oracle access to "weak" learner, which are utilized by iteratively making oracle calls with modified objective, in order to obtain a "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, we will in subsequent section obtain guarantees for the algorithms given in Section Oracle: Oracle: Denote by O a black-bor oracle to an (eo, approxxmmeee linear optimizer over a convex set K. Rd such that for any given v Id we have Ovv) 2 maX T ED.
Algorithm Non-convex Frank- Wolfe
1: Input: T' > 0, objective f. linear optimizer O, rate 1/--
2: Choose zo IC arbitrarily.
3: for t = 1, ' do
4: Call & (V,-)), where V v[(x)-1). Set = (1 m1) + 7.
5: end for
6: return == Ze where t' = arg mig V (zt - =x)).
Theorem 9. Let f: K RR be L-smooth in some norm ||,,,, bounded for all x E K. If(x)) H for some H > O, and let the diameter of K. in || ||. be D. Then, for a (Co, K2)-linear optimization
oracle O, and TJ: = / T. the output E of Algorithm satisfies
2HLD2
2x² max H}
max Vf(z) T (u x) < uERa
+ ED; max f(x'(())))))))))) f( - EK
+ +
T
T
Furthermore, if is (r, T, K1, -lo-lly gradient- and zo.... TT E Kc, then the output of Algorithm 4 Awhree nt m1, 22 satisfies the bound on the right.
We sketch the high-level ideas of the proof of our main result, stated in Theorem 7 and refer the reader to the appendix for the formal proof. We will establish an equivalence between RL Boosting (Algorithm [D and the variant of the Frank-Woll algorithm (Algorithm 4b. This abstraction allows us to obtain the novel convergence guarantees given in Theorem 7 Throughout the analysis, we use the notation V, " to denote the gradient of the value function with respect the |S| [il-sized representation of the policy म. namely the functional gradient of V*.
Internal- boosting weak learners. The Frank- Wolfe algorithm utilizes an inner gradient optimization oracle as a subroutine. To implement this oracle using approximate optimizers, we utilize yet another variant of the FW method as "internal-boowe bbossting" for the weak learners, by employing adapted analysis of [19] that is stated in Claim below. Let D, be the distribution induced by the trajectory sampler in round t.
Claim 10. Let 3 VI/aN, 12,
1}. oh produced by Algorithm satisfies x+))) s (2)A1/(1 - 7))a) (8 2/v
max ().D) (QTx(s)) EL,OW
8

---

From weak learning to linear optimization, Next, we give an important observation which allows us re-state the guarantee the previous subsection terms of linear optimization over functional gradients. The key observation here is that the expensive optimizing procedure for (V>V") n', which in particular requires iterating over all states in S, can be instead replaced with sampling from an appropriate distribution "D (via Algorithm 3 These sample pairs (s, (*,())))) could then be fed our weak learning algorithm, which guarantees generalization.
Lemma 11. Applying AlgorithmB]jo any given policy x yields an unbiased estimate of the gradient, such that for any n', (V+V)) = (...)
QT (s..))Tmt (e (-(ss)] / - 7), where xt 2'(:))) A "D is the distribution induced on the oulputs of Algorithm 3 for the policy æ and initial distribution
Experiments
The primary contribution of the present work is theoretical. Nevertheless, we empirically test our proposal with the experiment designed elicit qualitative properties of the proposed algorithm. instead of aiming to achieve the state-of-the-art. To validate our results, we check if the proposed algorithm indeed capable of boosting the accuracy of concrete instantiations of weak learners. We use depth-3 decision trees, with the implementation adapted from Scikit-Learn (30), as our base weak learner. This choice of weak learner is particularly suitable for boosting, because it is an impoverished policy class in representational sense and hence it is reasonable to expect that it may do only slightly better than random guessing with respect to the classification loss. We consider the performance of the boosting algorithm (Algorithm 1) across multiple rounds of boosting number of weak learners to that supervised-leamne -earnnin--nnn------- based policy iteration; the computational burden of the algorithm scales linearly with the latter. Throughout all the experiments, we used 0.9. To speed up computation, the plots below were generated by retaining the 3 most recent policies of every iteration in the policy mixture. We evaluated these on the CartPole and the LunarL.ander environments. The results demonstrate the proposed RI. boosting algorithm succeeds in maximizing rewards while using few weak learners (equivalently, within few rounds of boosting).
Boast N-
Boost N-20
Booet Ni:50
-25
Doost N:50
Boast No-100
Socat N-100
Decisin
Decision
300
-50
250
-75
150
100
-150
-175
0
15
Figure 2: Reward trajectory for the CartPole (left) and the LunarL_ander (right) environments of the proposed boosting algorithm for = 20, 50, 100 number of base weak learners is compared to supervised-leanae her----aannnnaassseeee policy iteration (decision tree) above. The x-axis corresponds to T number of iterations, and for each E [T'. reward is computed over 100 episodes of interactions. The confidence interval is plotted over such runs.
Conclusions
Building recent advances in boosting for online convex optimization and bandits, we have described a boosting algorithm for reinforcement learning over large state spaces with provable guarantees. We see this as a first attempt at using ried--nn-ttssed methodology from supervised learning to RL.

---

References
[1] Alekh Agarwal, Mikael Henaff, Sham Kakade, and Wen Sun. Pe-pg: Policy cover directed exploration for provable policy gradient learning. arXiv preprint arXiv:2007.0844 2020.
[2] Alckh Agarwal, Sham M Kakade, Jason Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. arXiv preprint arXiv: 2019.
[3] Naman Agarwal, Nataly Brukhim, Elad Hazan, and Zhou Lu. Boosting for control of dynamical systems. In International Conference on Machine Learning, pages 96-103. PMLR, 2020.
[4] Naman Agarwal, Brian Bullins, and Karan Singh. Variance-reduced conservative policy iteration. arXiv preprint arXiv:22/2.06255 2022.
[5] Noga Alon, Alon Gonen, Elad Hazan, and Shay Moran. Boosting simple learners. arXiv preprint arXiv:2001.
2020.
[6] 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.
[7] Alina Beygelzimer, Satyen Kale, and Haipeng Luo. Optimal and adaptive algorithms for online boosting. In International Conference on Machine Learning, pages 2323-2331, 2015.
[8] Alina Beygelzimer, John Langford, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandit algorithms with supervised learning guarantees. In Proceedings the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 19-26. JMLR Workshop and Conference Proceedings, 2011.
[9] Nataly Brukhim, Xinyi Chen, Elad Hazan, and Shay Moran. Online agnostic boosting via regret minimization. In Advances in Neural Information Processing Systems, 2020.
[10] Nataly Brukhim and Elad Hazan. Online boosting with bandit feedback. In Algorithmic Learning Theory, pages 397-420. PMLR, 2021.
[11] Lin Chen, Christopher Harshaw, Hamed Hassani, and Amin Karbasi. Projection-free online optimization with stochastic gradient: From convexity to submodularity. In International Conference on Machine Learning, pages 814-823, 2018.
[12] Shang- Tse Chen, Hsuan-Tien Lin, and Chi-Jen Lu. An online boosting algorithm with theoretical justifications. In Proceedings of the 29th International Coference on International Conference on Machine Learning, pages 1873-1880, 2012.
[13] Shang-Tse Chen, Hsuan-Tiee Lin, and Chi-Jen Lu. Boosting with online binary learners for the multiclass bandit problem. In International Conference on Machine Learning, pages 342-350, 2014.
[14] John Duchi, Shai Shalev-Shwartz, Yoram Singer, and Tushar Chandra. Efficient projections onto the 1-ball for learning in high dimensions. In Proceedings of the 25th international conference on Machine learning, pages 272-279, 2008
[15] Marguerite Frank and Philip Wolfe. An algorithm for quadratic programming. Naval research logistics quarterly, 3(1-))955-100, 1956.
[16] Hamed Hassani, Mahdi Soltanolkotabi. and Amin Karbasi. Gradient methods for submodular maximization. In Advances in Neural Information Processing Systems, pages 5841-5851, 2017.
[17] Elad Hazan. Introduction to online convex optimization. arXiv preprint arXiv: 1wXXvv:909.052000 2019.
[18] Elad Hazan, Sham Kakade, Karan Singh, and Abby Van Soest. Provably efficient maximum entropy exploration. International Conference on Machine Learning, pages 2681 1-691. PMLR, 2019.
10

---

[19] Elad Hazan and Karan Singh. Boosting for online convex optimization. arXiv preprint arXiv:2102.09305, 2021.
[20] Martin Jaggi. Revisiting frank-wolfe: Projection-free sparse convex optimization. In Interna- tional Conference on Machine Learning, pages 427-435. PMLR, 2013.
[21] Chi Jin, Zhuoran Yang. Zhaoran Wang, and Michael I Jordan. Provably efficient reinforcement learning with linear function approximation. Conference on Learning Theory, pages 2137- 2143. PMLR, 2020.
[22] Young Hun Jung, Jack Goetz, and Ambuj Tewari. Online multiclass boosting, Advances in neural information processing systems, pages 919-928, 2017.
[23] Young Hun Jung and Ambuj Tewari. Online boosting algorithms for multi-label ranking. In International Conference Artificial Intelligence and Statistics, pages 279-287, 2018.
[24] Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In In Proc. 19th International Conference Machine Learning. Citeseer, 2002.
[25] Varun Kanade and Adam Kalai. Potential-based agnostic boosting. In Advances in neural information processing systems, pages 880-888, 2009.
[26] Alessandro Lazaric and Rémi Munos. Hybrid stochasti-aadversarial on-line learning. In Conference on Learning Theory, 2009.
[27] Christian Leistner, Amir Saffari, Peter M Roth, and Horst Bischof. On robustness of on-line boosting-a competitive study. In IEEE 12th International Conference on Computer Vision Workshops, ICCV Workshops, pages 1362-1369. IEEE, 2009.
[28] Aryan Mokhtari, Hamed Hassani, and Amin Karbasi. Stochastic conditional gradient methods: From convex minimization to submodular maximization. arXiv preprint arXiv: arXiv:/804. 1804.880544 2018.
[29] Rémi Munos and Csaba Szepesvári. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 9(5), 2008
[30] Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. Scikit- learn: Machine learning in python. the Journal of machine Learning research, 12:2825-2830, 2011.
[31] Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online learning: Stochastic and constrained adversaries. arXiv preprint arXiv:
1eXiv:1104..0 104.5070, 2011.
[32] Robert E Schapire and Yoav Freund. Boosting: Foundations and Algorithms. MIT Press, 2012.
[33] Bruno Scherrer and Matthieu Geist. Local policy search in a convex space and conservative policy iteration as boosted policy search. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 35-50. Springer, 2014.
[34] Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Model-based rl in contextual decision processes: Pac bounds and exponential improvements over model-free approaches. In Conference on learning theory, pages 2898-2933. PMLR, 2019.
[35] Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. In S. Solla, T. Leen, and K. Müller, editors, Advances in Neural Information Processing Systems, volume 12. MIT Press, 2000.
[36] Yuanhao Wang, Ruosong Wang, and Sham M Kakade. An exponential lower bound for linearly-realzzable mdps with constant suboptimality gap. arXiv preprint arXiv:2 12690, 2021.
11

---

[37] Gellert Weisz, Philip Amortila, Barnabás Janzer, Yasin Abbasi- Yadkori, Nan Jiang, and Csaba Szepesvári. On query-efficient planning mdps under linear realizability of the optimal state-value function. arXiv preprint arXiv:2102.02049, 2021.
[38] Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforce- ment learning. Machine learning, 8(3-4):229-22) 256, 1992.
[39] Jiahao Xie, Zebang Shen, Chao Zhang, Hui Qian, and Boyu Wang. Stochastic recursive tradient-based methods for projection-free online learning. arXiv preprint arXiv: 191000999, 2019.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(C) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] in the supplementary material.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/relcasing new assets...
(a) your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
12


Reviews:
[{"review_id": "jesFH8G5zQ3", "reviewer": "Reviewer_2Czt", "summary": "This paper introduces the idea of boosting for reinforcement learning. \nIt presenting a boosting algorithm which outputs a policy by aggregating the policies suggested by a number of weak learners. \nThe sample complexity of the algorithm is analyzed theoretically. Effect of boosting is established both in theory, and with experiments.", "questions": "Main questions/comments:\n\n1) It is quite interesting to see how the sample complexity of the weak learner $m(\\epsilon, \\delta)$ translates to the one for the boosted learner. In particular, the new dependancy on $\\vert A \\vert^4$ in intriguing. Do you have any intuition on why the sudden dependancy on the size of the action set? Why does this only happen when only $\\alpha <1$? \n\n2) In general, would be interesting to see the $V^* - V^\\pi$ bound, where for a given $N$, $M$, $T$, and $\\gamma$, the error is worked out. A discussion on the terms of the right hand side of this bound (e.g. which results from the external boost, which comes from internal boost, and which is the oracle's error) would be insightful. \n\n3) How do the rates in Thm 7 and Cor 8 in general compare with sample complexity of other RL methods? (Only the dependence on $\\epsilon$ is compared.)\n\n4) I could not understand the rule for for calculating a base policy $\\mathcal A_n$. Can you explain the intuition behind constructing the new dataset? In particular what is $f_i$ and what do the terms in definition of $y_i$ present?\n\n5) Regarding the online weak learner: Is this necessary to consider a deterministic definition instead of having it hold with $1-\\delta$? \nCan you motivate one choice of assumption over the other? e.g. when the online oracle assumption makes more sense than the supervised learner. Generally, would have been nice if more of Appendix C was included in the main text. And to see how the resulting sample complexities are compare. \n\n6) Would be cool to read the opinion of the authors on which assumptions are artefacts of the analysis, and which can not be lifted. In particular, what would gain/lose by altering aspects of the oracle weak learner assumption. \n\n7) Assume there was computational limitations, and increasing $N$ the number of boosted weak learners would come at the cost of decreasing $M$. I am curious to know how these should be set in practice. Or, if there's a setup that would be generally more favorable? Judging by the bound I'm guessing we would benefit more from having many weak learners that are trained on smaller datasets?\n\n8) How important is $\\gamma$ in practice? Do we benefit a lot from larger $\\gamma$s? \n\n9) It seems to me that the reported experiment results are for single runs. For the plots to be meaningful, you should run the experiments with different random seeds and present the curves with the standard error. Although, without a doubt, boosting deems effective.\n\nTypos/small mistakes/notation issues:\n- [Line 25]: I think \"direct methods\" is supposed to be emphasized rather than \"so-called\"?\n- [Line 57-58]: I think some part of the sentence is accidentally erased.  \n- [Line 124]: This is slightly confusing, since the randomness is induced by both $\\pi$ and $P$.\n- [Line 151-152]: In the left hand side it should say $\\ell(\\mathcal{W}(D_m)(s))$. The $(s)$ is missing.\n- [Line 156]: It should be $\\pi \\in \\Pi$.\n- [Line 158]: Again I think it should be $\\Pi$.\n- [Line 248]: There's a space or \\n missing before \"Oracle\".\n- [Line 183-186]: I couldn't understand this part. Rewording would be nice.\n- [Algorithm 1]: $\\eta_{1,t}$ should also be listed as an input to the algorithm. \n- [Algorithm 1]: This is the first time that $M$ is used for the sample size of the weak learner. Better to be defined.\n- [Algorithm 2]: The notation $D_n$ used for the dataset of size $M$ of the $n$-th weak learner can be confused with notation $D_m$ in Def 2, which refers to a dataset of size $m$.\n- [Algorithm 2]: Line 5 should be $i \\in [M]$.\n- [Algorithm 2]: Not all of the input to the algorithm (e.g. $\\alpha$ and $\\eta_{2,n}$) are listed.\n- [Algorithm 3]: Again the input to the algorithm are not listed. In particular $\\gamma$.\n- [Line 204-206]: $\\mathcal E$ is used for the first time. I'm assuming $\\mathcal E := \\mathcal E_{d_0}$?\n- There's small issue with notation. The transition matrix $P$ of the MDP has the same notation as $P$ the number of rollouts/episodes.\n", "limitations": "Reading the paper, I can not tell how realistic is the weak oracle assumption for an $\\alpha$ that is sufficiently close to $1$. Specially in the case of the online weak learner. It is explained that this is a common assumption in the boosting literature. It is hard for me to see how this translates to when the dataset $D_m$ is sampled from a non-i.i.d. distribution (basically it is sampled via Alg 3).", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Originality/Significance.** I found the idea to be quite cool, can certainly imagine how weak learners can be practical in sequential settings. In general, I think revisiting basic techniques from supervised learning is a helpful practice for advancing the field and understanding certain limitations of it. I learned quite a bit while reviewing the paper and it immediately had me thinking about other areas in sequential learning which the idea of using weak learners would be useful. I think this paper can potentially inspire many follow up ideas.\n \nI am not thoroughly aware of this area of research and thus not in a place to comment about the contributions of the paper. This being said, and judging by the related works section, it seems to me that this paper is the first of its kind. Although, it seems that boosting was recently considered in the context of online learning. \n\n**Clarity/Quality.** The paper is written really well. It was easy to follow, while this is not my immediate area of research.\nI found the given background to be exactly enough. The contributions and the challenges were stated quite clearly. I couldn't understand Tables 1 and 2 right away, but after reading the paper this too became clear. More intuition could be given on certain design choices and the details of the algorithms. The theorems also lack interpretations, in my opinion.\n\nI should mention that I did not verify the correctness of the results. I only checked to see if the bounds behave the way I expect them with certain variables. Which they did. \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": "GtTDFrPipa_", "reviewer": "Reviewer_TxBq", "summary": "This paper proposes a boosting approach for Reinforcement learning. The authors provide sample and Oracle complexity guarantees for finding a near-optimal policy when a weak learner is available. The proposed method essentially implements the Frank-Wolfe (FW) algorithm where the objective is the value function $\\pi \\mapsto V^\\pi$ which is non-convex. However, thanks to a gradient dominance property of the value function, the FW algorithm is guaranteed to converge to a good solution. The weak learners are used within an internal boosting procedure to approximately (and efficiently) implement the FW procedure. ", "questions": "Is the following true: The idea of using FW algorithm in the context of RL was already explored by e.g. Agarwal et al, 2019, 2020. The main contribution of this paper is the efficient implementation of FW that leverages weak-learner?", "limitations": "The paper does not seem to be in a polished state yet. There are many typos that made it hard to follow certain points. Here, I list some of them (some are minor):\n- Line 87: distrbution -> distribution\n- Display just before line 124: there should not be a condition on \\pi and s in the definition of V^\\pi\n- Definition 2: should $\\ell$ be a 'gain' rather than a loss (you want to minimize losses and maximize gains)\n- Line 156: there is a reference to a policy tree (in math symbol), which is not defined yet.\n- Definition 3: seems incomplete. Are you using a particular projection map $\\Gamma$? The text before the definition suggests that you going to give the full details of the projection map. \n- Line 185: missing Lemma number\n- Line 1 of Alg 1. You say that the parameter $P$ is going to be passed to the internal boost (alg 2). I do not see any $P$ using within alg 2. Besides, I would recommend using another letter and reserving $P$ for the transition probability.\n- Line 4 of alg 1: $\\pi_t$ -> $\\pi_{t-1}$.\n- Alg 1 and Alg 2: list $\\eta_{1,t}$ and $\\eta_{2,t}$ as parameters of the algorithm.\n- line 207: the statement 'learning complexity $|\\mathcal{W}|$' is not precise (you did not say what it means to have a certain learning complexity)\n- Alg 2. You use both $D'_n$ and $D_{t,n}'$. Be consistent.\n- Line 249. You use both $\\mathcal{K}_2$ and $\\mathcal{K}$. Use just the former.\n- The second inequality in Theorem 9 (i.e. the RHS inequality just before line 251) should go after line 252. Currently, it suggests that Alg 4 achieves this guarantee without the gradient domination property.\n- It should be Algorithm 2 in Claim 10.\n- Line 276: testing -> test.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The high-level idea behind the proposed method is elegant. This idea consists of using weak learners and a boosting procedure to efficiently implement an approximate linear optimization oracle over the space of policy and then using it to run the FW algorithm to optimize the value function. Although the idea of using the FW algorithm in the context of RL does not seem to be new,\n\nHowever, the presentation could be improved in my opinion. For example, the workings of the internal boosting procedure Algorithm 2 are never really explained in the main body. Given that this is a major component of the proposed method, explanations of the step of the algorithm should be included in the main body. A high-level sketch of Claim 10 would also be good.", "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