# A Boosting Approach to Reinforcement Learning

Nataly Brukhim
Princeton University
<EMAIL_ADDRESS>
&Elad Hazan
Princeton University
Google AI Princeton
<EMAIL_ADDRESS>
&Karan Singh
Microsoft Research
<EMAIL_ADDRESS>

###### 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 accurate 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, till global optimality is reached. 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
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
convergence.

##  1 Introduction

The field of reinforcement learning, formally modelled as learning in Markov
decision processes (MDP), models the mechanism of learning from rewards, as
opposed to examples. Although the case of tabular MDPs is well understood, the
main difficulty in applying RL to practice is the explosion 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 is
known to 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 in 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 we study another methodology to derive provable algorithms for
reinforcement learning: 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
[29] to reinforcement learning. Interestingly, however, our resulting
aggregation of weak learners is not linear.

In order to circumvent the computational hardness of solving general MDPs with
function approximation, 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. We describe
an algorithm that iteratively calls this procedure on carefully constructed
new objectives, and aggregates the solution into a 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,

  1. (a)

The value function is not a convex or concave function of the policy. This is
true even in the tabular case, and even more so if we use a parameterized
policy class.

  2. (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.

  3. (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 can hope for a
multiplicative and/or additive approximation of the overall value.

Our approach overcomes these challenges by applied several new as well as
recently developed techniques. To overcome the nonconvexity of the value
function, we use a novel variant of the Frank-Wolfe optimization algorithm
that simultaneously delivers on two guarantees. First, it finds a first order
stationary point with near-optimal rate. Secondly, if the objective happens to
admit a certain gradient domination property, an important generalization of
convexity, it also guarantees near optimal value. The application of the
nonconvex Frank-Wolfe 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 information-theoretic challenge of the unknown transition function
is overcome by careful 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 a
multiplicative approximation, which is critical for our application. Luckily,
recent work in the area of online convex optimization [18] studies boosting
with a multiplicative weak learner. We make critical use of this new technique
which includes a non-linear aggregation (using a 2-layer neural network) of
the weak learners. This aspect is 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 a certain policy
class.

The output of the algorithm is a 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 a result of
the two-tier structure of our algorithm: an 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).

Supervised weak learner Online weak learner Episodic model
$C^{6}_{\infty}(\mathbbl{\Pi})/\alpha^{4}\varepsilon^{5}$
$C^{4}_{\infty}(\mathbbl{\Pi})/\alpha^{2}\varepsilon^{3}$
$C_{\infty}=\max_{\pi\in\mathbbl{\Pi}}\left\|\frac{d^{\pi^{*}}}{d^{\pi}}\right\|_{\infty}$
Rollouts w. $\nu$-resets $\mathcal{D}_{\infty}^{6}/\alpha^{4}\varepsilon^{6}$
$\mathcal{D}_{\infty}^{4}/\alpha^{2}\varepsilon^{4}$
$D_{\infty}=\left\|\frac{d^{\pi^{*}}}{\nu}\right\|_{\infty}$
---
Table 1: Sample complexity of the proposed algorithms for different
$\alpha$-weak learning models (supervised & online) and modes of accessing the
MDP (rollouts & rollouts with reset distribution $\nu$), suppressing
polynomial factors in $|A|,1/(1-\gamma)$. See Theorem 12 for details.

###  1.3 Related work

To cope with prohibitively large MDPs, the method of choice to approximate the
policy and transition 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 autonomous
driving. In terms of provable methods for deep RL, there are two main lines of
work. The first is a robust analysis of the policy gradient algorithm [2, 1].
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.

The other line of work for provable approaches is policy iteration, which uses
a restricted policy class, making incremental updates, such as Conservative
Policy Iteration (CPI) [22, 30], and Policy Search by Dynamic Programming
(PSDP)[5].

Our boosting approach for provable deep RL builds on the vast literature of
boosting for supervised learning [29], and recently online learning [25, 12,
13, 7, 20, 21]. 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 a multiplicative weak learner
[18]. This latter technique implies a non-linear aggregation of the weak
learners. Non-linear boosting was only recently investigated in the context of
classification [4], where it was shown to potentially enable significantly
more efficient boosting.

Perhaps the closest work to ours is boosting in the context of control of
dynamical systems [3]. However, this work critically requires knowledge of the
underlying dynamics (transitions), which we do not, and cannot cope with a
multiplicative approximate weak learner.

The Frank-Wolfe algorithm is extensively used in machine learning, see e.g.
[19], references therein, and recent progress in stochastic Frank-Wolfe
methods [15, 26, 11, 33]. Recent literature has applied a variant of this
algorithm to reinforcement learning in the context of state space exploration
[17].

##  2 Preliminaries

#### Optimization.

We say that a differentiable function $f:\mathcal{K}\mapsto\mathbb{R}$ over
some domain $\mathcal{K}$ is $L$-smooth with respect to some norm
$\|\cdot\|_{*}$ if for every $x,y\in\mathcal{K}$ we have

$\left|f(y)-f(x)-\nabla\mkern-2.5muf(x)^{\top}(y-x)\right|~{}\leq~{}\frac{L}{2}\|x-y\|_{*}^{2}.$

For constrained optimization (such as over $\Delta_{A}$), the projection
$\Gamma:\mathbb{R}^{|A|}\to\Delta_{A}$ of a point $x$ to onto a domain
$\Delta_{A}$ is

$\Gamma[x]=\operatorname*{arg\,min}_{y\in\Delta_{A}}\|x-y\|.$

An important generalization of convex function we use henceforth is that of
gradient domination,

######  Definition 1 (Gradient Domination).

A function $f:\mathcal{K}\to\mathbb{R}$ is said to be
$(\kappa,\tau,\mathcal{K}_{1},\mathcal{K}_{2})$-locally gradient dominated
(around $\mathcal{K}_{1}$ by $\mathcal{K}_{2}$) if for all
$x\in\mathcal{K}_{1}$, it holds that

$\max_{y\in\mathcal{K}}f(y)-f(x)~{}\leq~{}\kappa\times\max_{y\in\mathcal{K}_{2}}\left\\{\nabla\mkern-2.5muf(x)^{\top}(y-x)\right\\}+\tau.$

#### Markov decision process.

An infinite-horizon discounted Markov Decision Process (MDP)
$M=(S,A,P,r,\gamma,d_{0})$ is specified by: a state space $S$, an action space
$A$, a transition model $P$ where $P(s^{\prime}|s,a)$ denotes the probability
of immediately transitioning to state $s^{\prime}$ upon taking action $a$ at
state $s$, a reward function $r:S\times A\rightarrow[0,1]$ where $r(s,a)$ is
the immediate reward associated with taking action $a$ at state $s$, a
discount factor $\gamma\in[0,1)$; a starting state distribution $d_{0}$ over
$S$. For any infinite-length state-action sequence (hereafter, called a
trajectory), we assign the following value

$V(\tau=(s_{0},a_{0},s_{1},a_{1},\dots))=\sum_{t=0}^{\infty}\gamma^{t}r(s_{t},a_{t}).$

The agent interacts with the MDP through the choice of stochastic policy
$\pi:S\to\Delta_{A}$ it executes, where $\Delta_{A}$ denotes the probability
simplex over $A$. The execution of such a policy induces a distribution over
trajectories $\tau=(s_{0},a_{0},\dots)$ as

$P(\tau|\pi)=d_{0}(s_{0})\prod_{t=0}^{\infty}(P(s_{t+1}|s_{t},a_{t})\pi(a_{t}|s_{t})).$
(1)

Using this description we can associate a state $V^{\pi}(s)$ and state-action
$Q^{\pi}(s,a)$ value function with any policy $\pi$. For an arbitrary
distrbution $d$ over $S$, define:

$Q^{\pi}(s)={\mathbb
E}\Bigg{[}\sum_{t=0}^{\infty}\gamma^{t}r(s_{t},a_{t})\Big{|}\
\pi,s_{0}=s,a_{0}=a\Bigg{]},$ $V^{\pi}(s)={\mathbb
E}_{a\sim\pi(\cdot|s)}\left[Q^{\pi}(s,a)|\pi,s\right],\qquad
V^{\pi}_{d}={\mathbb E}_{s_{0}\sim d}\left[V^{\pi}(s)|\pi\right].$

Here the expectation is with respect to the randomness of the trajectory
induced by $\pi$ in $M$. When convenient, we shall use $V^{\pi}$ to denote
$V^{\pi}_{d_{0}}$, and $V^{*}$ to denote $\max_{\pi}V^{\pi}$.

Similarly, to any policy $\pi$, one may ascribe a (discounted) state-
visitation distribution $d^{\pi}=d^{\pi}_{d_{0}}$.

$d^{\pi}_{d}(s)=(1-\gamma)\sum_{t=0}^{\infty}\gamma^{t}\sum_{\tau:s_{t}=s}P(\tau|\pi,s_{0}\sim
d)$

#### 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 a policy, stop and restart at any
point, and do this multiple times.

Another interaction model we consider is called rollout with $\nu$-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 $\nu\neq d_{0}$.
This interaction model was considered in prior work on policy optimization
[22, 2]. The motivation for this model is two-fold: first, $\nu$ can be used
to incorporate priors (or domain knowledge) about the state coverage of the
optimal policy; second, $\nu$ provides a mechanism to incorporate exploration
into policy optimization procedures.

##  3 Setting: Policy Aggregation and Weak Learning

Our boosting algorithms henceforth call upon weak learners to generate weak
policies, and aggregate these policies in a way that guarantees eventual
convergence to optimality. In this section we formalize both components.

###  3.1 Policy aggregation

For a base class of policies $\Pi_{W}$, 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 $N_{0}\in\mathbb{Z}_{+}$, $w\in\mathbb{R}^{N_{0}}$, $(f_{1},\dots
f_{N_{0}})\in(S\to\mathbb{R}^{|A|})^{\otimes N_{0}}$, we define
$f=\sum_{n=1}^{N_{0}}w_{n}f_{n}$ to be the unique function
$f:S\to\mathbb{R}^{A}$ for which simultaneously for all $s\in S$, it holds

$f(s)=\sum_{n=1}^{N_{0}}w_{n}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 $\mathbb{R}^{|A|}$ produces a policy, i.e. a mapping from states
to distributions over actions.

######  Definition 3 (Policy Projection).

Given a function $f:S\to\mathbb{R}^{|A|}$, define a projected policy
$\pi=\Gamma[f]$ to be a policy such that simultaneously for all $s\in S$, it
holds that $\pi(\cdot|s)=\Gamma\left[f(s)\right].$

The next definition defines the class of functions represented by circuits of
depth $1$ over a base policy class. Note that these function do not
necessarily represent policies since they take an affine (vs. convex)
combination of policies.

######  Definition 4 (Shrub).

For an arbitrary base policy class $\Pi\subseteq S\to\Delta_{A}$, define
$\mathbbl{\Lambda}(\Pi,N)$ to be a set such that $\lambda\in\Lambda(\Pi,N)$ if
and only if there exists
$N_{0}~{}\leq~{}N,w\in\mathbb{R}^{N_{0}},(\pi_{1},\dots\pi_{N_{0}})\in\Pi^{\otimes
N_{0}}$ such that $\lambda=\sum_{n=1}^{N_{0}}w_{n}\pi_{n}$.

The final definition describes the set of possible outputs of the boosting
procedure.

######  Definition 5 (Policy Tree).

For an arbitrary base policy class $\Pi\subseteq S\to\Delta_{A}$, define
$\mathbbl{\Pi}(\Pi,N,T)$ to be a policy class such that
$\pi\in\mathbbl{\Pi}(\Pi,N,T)$ if and only if there exists
$T_{0}~{}\leq~{}T,w\in\Delta_{T_{0}},(\lambda_{1},\dots\lambda_{T_{0}})\in\mathbbl{\Lambda}(\Pi,N)^{\otimes
T_{0}}$ such that $\pi=\sum_{t=1}^{T_{0}}w_{t}\Gamma[\lambda_{t}]$.

It is important that the policy that the boosting algorithm outputs can be
evaluated efficiently. To this end, we make the following claim.

######  Claim 6.

For any $\pi\in\mathbbl{\Pi}(\Pi,N,T)$, $\pi(\cdot|s)$ for any $s\in S$ can be
evaluated using $TN$ base policy evaluations and $O(T\times(NA+A\log A))$
arithmetic and logical operations.

###### Proof.

Since $\pi\in\mathbbl{\Pi}(\Pi,N,T)$, it is composed of $TN$ base policies.
Producing each aggregated function takes $NA$ additions and multiplications;
there are $T$ of these. Each projection takes time equivalent to sorting $|A|$
numbers, due to a water-filling algorithm [14]; these are also $T$ in number.
The final linear transformation takes an additional $TA$ operations. ∎

$\bar{\pi}$
---
$\Gamma[\lambda_{2}]$$\lambda_{1}\ $$\pi_{1}$$w_{1}\
$$\pi_{2}$$\pi_{3}$$w_{1}^{\prime}\ \ \ $$\Gamma[\lambda_{2}]$$\
\lambda_{2}$$\pi_{4}$$\pi_{5}$$\pi_{6}$$\ w_{6}$$\ \ w_{2}^{\prime}$ A Shrub
---
$\lambda_{t}\in\mathbbl{\Lambda}(\Pi,N)$
A Policy Tree
---
$\bar{\pi}\in\mathbbl{\Pi}(\Pi,N,T)$
Figure 1: The figure illustrates a Policy Tree hierarchy (see Definition 5),
obtained by setting $N=3$ on the inner loop, and $T=2$ on the outer loop, to
overall get all base policies $\pi_{1},...,\pi_{6}\in\Pi_{W}$ on the lower
level. The middle level holds $T=2$ Policy Shurbs (see Definition 4), where
each Shrub $\lambda_{t}\in\mathbbl{\Lambda}(\Pi,N)$ is an aggregation of base
policies. The top level is an weighted aggregation of the projected shrubs
$\Gamma[\lambda_{t}]$ , which forms the overall Policy Tree
$\bar{\pi}\in\mathbbl{\Pi}(\Pi,N,T)$.

###  3.2 Models of weak learning

We consider two types of weak learners, and give different end results based
on the different assumptions: weak supervised and weak online learners. In the
discussion below, let $\pi_{r}$ be a uniformly random policy, i.e.
$\forall(s,a)\in S\times A,\pi_{r}(a|s)=1/|A|$.

#### Supervised Learning.

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 at 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
[23, 9, 18] that defines a weak learner as one that can approximate the best
policy in a given policy class.

######  Definition 7 (Weak Supervised Learner).

Let $\alpha\in(0,1)$. Consider a class $\mathcal{L}$ of linear loss functions
$\ell:\mathbb{R}^{A}\to\mathbb{R}$, and $\mathbb{D}$ a family of distributions
that are supported over $S\times\mathcal{L}$, policy classes $\Pi_{W},\Pi$. A
weak supervised learning algorithm, for every $\varepsilon,\delta>0$, given
$m(\varepsilon,\delta)$ samples $D_{m}$ from any distribution
$\mathcal{D}\in\mathbb{D}$ outputs a policy $\mathcal{W}(D_{m})\in\Pi_{W}$
such that with probability $1-\delta$,

$\displaystyle\mathbb{E}_{(s,\ell)\sim\mathcal{D}}\big{[}\ell(\mathcal{W}(D_{m}))\big{]}~{}\geq~{}\alpha\max_{\pi^{*}\in\Pi}\mathbb{E}_{(s,\ell)\sim\mathcal{D}}\big{[}\ell(\pi^{*}(s))\big{]}+(1-\alpha)\mathbb{E}_{(s,\ell)\sim\mathcal{D}}\big{[}\ell(\pi_{r}(s))\big{]}-\varepsilon.$

Note that the weak learner outputs a policy in $\Pi_{W}$ which is
approximately competitive against the class $\Pi$. 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 $\mathbbl{\Pi}(\Pi_{W},N,T)$ as $\mathbbl{\Pi}$ for
$N,T=O(\mathrm{poly}(|A|,(1-\gamma)^{-1},\varepsilon^{-1},\alpha^{-1},\log\delta^{-1}))$
specified later.

######  Assumption 1 (Weak Supervised Learning).

The booster has access to a weak supervised learning oracle (Definition 7)
over the policy class $\Pi$, for some $\alpha\in(0,1)$. Furthermore, the weak
learning condition holds only for a class of _natural_ distributions
$\mathbb{D}$ – $\mathcal{D}\in\mathbb{D}$ if and only if there exists some
$\pi\in\mathbbl{\Pi}$ such that

$\mathcal{D}_{S}(s)=\int_{\ell}\mathcal{D}(s,\ell)d\mu(\ell)=d^{\pi}(s).$

In particular, while a _natural_ distribution may have arbitrary distribution
over labels, its marginal distribution over states must be realizable as the
state distribution of some policy in $\mathbbl{\Pi}$ 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 not affect the distribution of states (say $d_{0}$), it is sufficient that
the weak learning condition holds with respect to all couplings of a single
distribution $d_{0}$.

#### Online Learning.

The second model of weak learning we consider requires a stronger assumption,
but will give us better sample and oracle complexity bounds henceforth.

######  Definition 8 (Weak Online Learner).

Let $\alpha\in(0,1)$. Consider a class $\mathcal{L}$ of linear loss functions
$\ell:\mathbb{R}^{A}\to\mathbb{R}$. A weak online learning algorithm, for
every $M>0$, incrementally for each timestep computes a policy
$\mathcal{W}_{m}\in\Pi_{W}$ and then observes the state-loss pair
$(s,\ell_{t})\in S\times\mathcal{L}$ such that

$\displaystyle\sum_{m=1}^{M}\ell_{m}(\mathcal{W}_{m}(s_{m}))~{}\geq~{}\alpha\max_{\pi^{*}\in\Pi}\sum_{m=1}^{M}\ell_{m}(\pi^{*}(s_{m}))+(1-\alpha)\sum_{m=1}^{M}\ell_{m}(\pi_{r}(s_{m}))-R_{\mathcal{W}}(M).$

######  Assumption 2 (Weak Online Learning).

The booster has access to a weak online learning oracle (Definition 8) over
the policy class $\Pi$, for some $\alpha\in(0,1)$.

######  Remark 9.

A similar remark about _natural_ distributions applies to the online weak
learner. In particular, it is sufficient the guarantee in 8 holds for
arbitrary sequence of loss functions with high probability over the sampling
of the state from $d^{\pi}$ for some $\pi\in\mathbbl{\Pi}$. Although stronger
than supervised weak learning, this oracle can be interpreted as a relaxation
of the online weak learning oracle considered in [9, 10, 18]. A similar model
of hybrid adversarial-stochastic online learning was considered in [28, 24,
8]. In particular, it is known [24] that unlike online learning, the capacity
of a hypothesis class for this model is governed by its VC dimension (vs.
Littlestone dimension).

##  4 Algorithm & Main Results

In this section we describe our RL boosting algorithm. Here we focus on the
case where a 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.

#### Smoothing & Extension.

Define the inf-convolution smoothing operator as follows [6]:

$M_{\beta}[f](x)=\min_{y\in\Delta_{A}}\left\\{f(y)+\frac{1}{2\beta}\|x-y\|^{2}\right\\}$

The extension operator [18] operate overs functions and modifies their value
outside and near the boundary of the convex set $\Delta_{A}$ to aid the
boosting algorithm.

$F_{G,\beta}[f](x)=M_{\beta}\left[f(x)+G\min_{y\in\Delta_{A}}\|y-x\|\right]$

To state the results, we need the following definitions. The first generalizes
the policy completeness notion from [30]. It may be seen as the policy-
equivalent analogue of inherent bellman error [27]. Intuitively, it measures
the degree to which a policy in $\Pi$ can best approximate the bellman
operator in an average sense with respect to the state distribution induced by
a policy from $\mathbbl{\Pi}$.

######  Definition 10 (Policy Completeness).

For any initial state distribution $\mu$, define

$\mathcal{E}_{\mu}(\mathbbl{\Pi},\Pi)=\max_{\pi\in\mathbbl{\Pi}}\min_{\pi^{*}\in\Pi}{\mathbb
E}_{s\sim d^{\pi}_{\mu}}\left[\max_{a\in
A}Q^{\pi}(s,a)-Q^{\pi}(s,\cdot)^{\top}\pi^{*}(\cdot|s)\right].$

The following notion of the distribution mismatch coefficient is often useful
to characterize the exploration problem faced by policy optimization
algorithms.

######  Definition 11 (Distribution Mismatch).

Let $\pi^{*}=\operatorname*{arg\,max}_{\pi}V^{\pi}$, and $\nu$ a fixed initial
state distribution (see section 2). Define the following distribution mismatch
coefficients:

$C_{\infty}(\mathbbl{\Pi})=\max_{\pi\in\mathbbl{\Pi}}\left\|\frac{d^{\pi^{*}}}{d^{\pi}}\right\|_{\infty},\qquad
D_{\infty}=\left\|\frac{d^{\pi^{*}}}{\nu}\right\|_{\infty}.$

###  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 a step size, provided in the appendix.

Algorithm 1 RL Boosting via Weak Supervised Learning

1: Initialize a policy $\pi_{0}\in\Pi_{W}$ arbitrarily.

2: for $t=1$ to $T$ do

3: Set $\rho_{t,0}$ to be an arbitrary policy in $\Pi_{W}$.

4: for $n=1$ to $N$ do

5: Execute $\pi_{t-1}$ for $M$ episodes with initial state distribution $\mu$
via Algorithm 2, to get  $D_{t,n}=\\{(s_{i},\widehat{Q_{i}})_{i=1}^{m}\\}.$

6: Modify $D_{t,n}$ to produce a new dataset
$D^{\prime}_{t,n}=\\{(s_{i},f_{i})\\}_{i=1}^{m}$, such that for all $i\in[m]$:
$f_{i}=-\nabla\mkern-2.5muF_{G,\beta}[-\widehat{Q}_{i}](\rho_{t,n}(\cdot|s_{i}))$
.

7: Let $\mathcal{A}_{t,n}$ be the policy chosen by the weak learning oracle
when given data set $D^{\prime}_{t,n}$.

8: Update
$\rho_{t,n}=(1-\eta_{2,n})\rho_{t,n-1}+\frac{\eta_{2,n}}{\alpha}\mathcal{A}_{t,n}-\eta_{2,n}\left(\frac{1}{\alpha}-1\right)\pi_{r}$.

9: end for

10: Declare $\pi^{\prime}_{t}=\Gamma\left[\rho_{t,N}\right]$.

11: Choose $\eta_{1,t}=\min\\{1,\frac{2C_{\infty}(\mathbbl{\Pi})}{t}\\}$ if
$\mu=d_{0}$ else
$\eta_{1,t}=\texttt{\small{StepChooser}}(\pi_{t-1},\pi^{\prime}_{t},\mu,P)$.

12: Update $\pi_{t}=(1-\eta_{1,t})\pi_{t-1}+\eta_{1,t}\pi^{\prime}_{t}$.

13: end for

14: Output $\bar{\pi}$=$\pi_{T}$ if $\mu=d_{0}$ else output $\pi_{t-1}$ with
the smallest $\eta_{t}$.

######  Theorem 12.

Algorithm 1 samples $T(MN+P)$ episodes of length
$\frac{1}{1-\gamma}\log\frac{T(MN+P)}{\delta}$ with probability $1-\delta$. In
the episodic model, Algorithm 1 guarantees as long as
$T=\frac{16C^{2}_{\infty}(\mathbbl{\Pi})}{(1-\gamma)^{3}\varepsilon}$,
$N=\left(\frac{16|A|C_{\infty}(\mathbbl{\Pi})}{(1-\gamma)^{2}\alpha\epsilon}\right)^{2}$,
$M=m\left(\frac{(1-\gamma)^{2}\alpha\varepsilon}{8C_{\infty}(\mathbbl{\Pi})|A|},\frac{\delta}{NT}\right)$,$\mu=d_{0}$,
we have with probability $1-\delta$

$V^{*}-V^{\pi}~{}\leq~{}C_{\infty}(\mathbbl{\Pi})\frac{\mathcal{E}(\mathbbl{\Pi},\Pi)}{1-\gamma}+\varepsilon$

In the $\nu$-reset model, Algorithm 1 guarantees as long as
$T=\frac{8D^{2}_{\infty}}{(1-\gamma)^{6}\varepsilon^{2}}$,
$N=\left(\frac{16|A|D_{\infty}}{(1-\gamma)^{3}\alpha\epsilon}\right)^{2}$,
$P=\frac{200|A|^{2}D_{\infty}^{2}}{(1-\gamma)^{6}\varepsilon^{2}}\log\frac{2TN}{\delta}$,
$M=m\left(\frac{(1-\gamma)^{3}\alpha\varepsilon}{8|A|D_{\infty}},\frac{\delta}{2NT}\right)$,$\mu=\nu$,
we have with probability $1-\delta$

$V^{*}-V^{\pi}~{}\leq~{}D_{\infty}\frac{\mathcal{E}_{\nu}(\mathbbl{\Pi},\Pi)}{(1-\gamma)^{2}}+\varepsilon$

If
$m(\varepsilon,\delta)=\frac{\log|{\mathcal{W}}|}{\varepsilon^{2}}\log\frac{1}{\delta}$
for some measure of weak learning complexity $|{\mathcal{W}}|$, the algorithm
samples
$\tilde{O}\left(\frac{C_{\infty}^{6}(\mathbbl{\Pi})|A|^{4}\log|{\mathcal{W}}|}{(1-\gamma)^{11}\alpha^{4}\varepsilon^{5}}\right)$
episodes in the episodic model, and
$\tilde{O}\left(\frac{D_{\infty}^{6}|A|^{4}\log|{\mathcal{W}}|}{(1-\gamma)^{18}\alpha^{4}\varepsilon^{6}}\right)$
in the $\nu$-reset model.

###  4.2 Trajectory sampler

In Algorithm 2 we describe an episodic sampling procedure, that is used in our
sample-based RL boosting algorithms described above. For a fixed initial state
distribution $\mu$, and any given policy $\pi$, we apply the following
sampling procedure: start at an initial state $s_{0}\sim\mu$, and continue to
act thereafter in the MDP according to any policy $\pi$, until termination.
With this process, it is straightforward to both sample from the state
visitation distribution $s\sim d^{\pi}$, and to obtain unbiased samples of
$Q^{\pi}(s,\cdot)$; see Algorithm 2 for the detailed process.

1: Sample state $s_{0}\sim\mu$, and action $a^{\prime}\sim\mathcal{U}(A)$
uniformly.

2: Sample $s\sim d^{\pi}$ as follows: at every timestep $h$, with probability
$\gamma$, act according to $\pi$; else, accept $s_{h}$ as the sample and
proceed to Step 3.

3: Take action $a^{\prime}$ at state $s_{h}$, then continue to execute $\pi$,
and use a termination probability of $1-\gamma$. Upon termination, set
$R(s_{h},a^{\prime})$ as the _undiscounted_ sum of rewards from time $h$
onwards.

4: Define the vector $\widehat{Q^{\pi}_{s_{h}}}$, such that for all $a\in A$,
$\widehat{Q^{\pi}_{s_{h}}}(a)=|A|\cdot
R(s_{h},a^{\prime})\cdot\mathbb{I}_{a=a^{\prime}}$.

5: return $(s_{h},\widehat{Q^{\pi}_{s_{h}}})$.

Algorithm 2 Trajectory Sampler: $s\sim d^{\pi}$, unbiased estimate of
$Q^{\pi}_{s}$

##  5 Analysis

Throughout the analysis, we use the notation $\nabla\mkern-2.5mu_{\pi}V^{\pi}$
to denote the gradient of the value function with respect to the
$|S|\times|A|$-sized representation of the policy $\pi$, namely the functional
gradient of $V^{\pi}$.

###  5.1 Internal-boosting weak learners

We utilize a variant of the Frank-Wolfe method as a form “internal-boosting”
for the weak learners, by employing an adapted analysis of previous work that
is stated below.

Note that $\widehat{Q}^{\pi}(s,\cdot)$ produced by Algorithm 2 satisfies
$\|\widehat{Q}^{\pi}(s,\cdot)\|=\frac{|A|}{1-\gamma}$. We can now borrow the
following result on boosting for statistical learning from [18], specializing
the decision set to be $\Delta_{A}$. Let $\mathcal{D}_{t}$ be the distribution
induced by the trajectory sampler in round $t$.

######  Theorem 13 ([18]).

Let $\beta=\sqrt{\frac{1}{\alpha N}}$, and
$\eta_{2,n}=\min\\{\frac{2}{n},1\\}$. Then, for any $t$, $\pi^{\prime}_{t}$
produced by Algorithm 1 satisfies with probability $1-\delta$ that

$\max_{\pi\in\Pi}\mathbb{E}_{(s,Q)\sim\mathcal{D}_{t}}\left[Q^{\top}\pi(s)\right]-\mathbb{E}_{(s,Q)\sim\mathcal{D}_{t}}\left[Q^{\top}\pi^{\prime}_{t}(s)\right]~{}\leq~{}\frac{2|A|}{(1-\gamma)\alpha}\left(\frac{2}{\sqrt{N}}+\varepsilon\right)$

###  5.2 From weak learning to linear optimization

In the following Lemma, we give an important observation which allows us to
re-state the guarantee in the previous subsection in terms of linear
optimization over functional gradients.

######  Lemma 14.

Applying Algorithm 2 for any given policy $\pi$, yields an unbiased estimate
of the gradient, such that for any $\pi^{\prime}$,

$(\nabla\mkern-2.5mu_{\pi}V_{\mu}^{\pi})^{\top}\pi^{\prime}=\frac{1}{1-\gamma}{\mathbb
E}_{(s,\widehat{Q^{\pi}}(s,\cdot))\sim\mathcal{D}}\Big{[}\widehat{Q^{\pi}}(s,\cdot)^{\top}\pi^{\prime}(\cdot|s)\Big{]},$
(2)

where $\pi^{\prime}(\cdot|s)\in\Delta_{A}$, and $\mathcal{D}$ is the
distribution induced on the outputs of Algorithm 2, for a given policy $\pi$
and initial state distribution $\mu$.

###### Proof.

Recall $\nabla\mkern-2.5mu_{\pi}V^{\pi}$ denotes the gradient with respect to
the $|S|\times|A|$-sized representation of the policy $\pi$ – the functional
gradient. Then, using the policy gradient theorem [32, 31], it is given by,

$\frac{\partial
V_{\mu}^{\pi}}{\partial\pi(a|s)}=\frac{1}{1-\gamma}d^{\pi}_{\mu}(s)Q^{\pi}(s,a).$
(3)

The following sources of randomness are at play in the sampling algorithm
(Algorithm 2): the distribution $d^{\pi}$ (which encompasses the discount-
factor-based random termination, the transition probability, and the
stochasticity of $\pi$), and the uniform sampling over $A$. For a fixed
$s,\pi$, denote by $\mathcal{Q}^{\pi}_{s}$ as the distribution over
$\widehat{Q^{\pi}}(s,\cdot)\in\mathbb{R}^{A}$, induced by all the
aforementioned randomness sources. To conclude the claim, observe that by
construction

${\mathbb
E}_{\mathcal{Q}^{\pi}(s,\cdot)}[\widehat{Q^{\pi}}(s,\cdot)|\pi,s]=Q^{\pi}(s,\cdot).$
(4)

∎

###  5.3 Main result - proof overview

Next we sketch the high-level ideas of the proof of our main result, stated in
Theorem 12. We refer the reader to the appendix for the formal proof. First,
we provide an abstract high-level procedural template that our RL booster
operates in. It is based on a novel variant of the Frank-Wolfe (FW)
optimization technique adapted to non-convex and gradient dominated function
classes. The broad scheme here is compounded of several components.

We utilize a variant of the FW method as “internal-boosting” for the weak
learners (by employing an adapted analysis of Theorem 13), using the
observation given in the previous section. This is procedure is enveloped by
our novel variant of the FW method for non-convex settings. Lastly, the result
stems from demonstrating that the value function satisfy gradient domination
properties, in the different settings considered, for which the guarantees of
the high-level algorithm hold.

##  6 Conclusions

Building on 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 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 an RL agent with
multiplicative optimality guarantee, and it would be interesting to extend our
methodology to this notion of weak learnability.

Another important aspect that is not discussed in our paper is that of state-
space exploration. Potentially boosting can be combined with state-space
exploration techniques to give stronger guarantees independent of distribution
mismatch $C_{\infty},D_{\infty}$ 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?

Remark on broad societal impacts. Reinforcement learning has numerous
applications that are beneficial (in healthcare, education) as well as
damaging (i.e. polarization via recommendations). Our work advances the theory
of reinforcement learning, and we acknowledge that upon further development it
can be potentially used to either end.

## References

  * [1] Alekh Agarwal, Mikael Henaff, Sham Kakade, and Wen Sun.  Pc-pg: Policy cover directed exploration for provable policy gradient learning.  arXiv preprint arXiv:2007.08459, 2020.
  * [2] Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan.  On the theory of policy gradient methods: Optimality, approximation, and distribution shift.  arXiv preprint arXiv:1908.00261, 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] Noga Alon, Alon Gonen, Elad Hazan, and Shay Moran.  Boosting simple learners.  arXiv preprint arXiv:2001.11704, 2020.
  * [5] 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.
  * [6] Amir Beck.  First-order methods in optimization.  SIAM, 2017.
  * [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 of 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-Tien 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 l 1-ball for learning in high dimensions.  In Proceedings of the 25th international conference on Machine learning, pages 272–279, 2008.
  * [15] Hamed Hassani, Mahdi Soltanolkotabi, and Amin Karbasi.  Gradient methods for submodular maximization.  In Advances in Neural Information Processing Systems, pages 5841–5851, 2017.
  * [16] Elad Hazan.  Introduction to online convex optimization.  arXiv preprint arXiv:1909.05207, 2019.
  * [17] Elad Hazan, Sham Kakade, Karan Singh, and Abby Van Soest.  Provably efficient maximum entropy exploration.  In International Conference on Machine Learning, pages 2681–2691. PMLR, 2019.
  * [18] Elad Hazan and Karan Singh.  Boosting for online convex optimization.  arXiv preprint arXiv:2102.09305, 2021.
  * [19] Martin Jaggi.  Revisiting frank-wolfe: Projection-free sparse convex optimization.  In International Conference on Machine Learning, pages 427–435. PMLR, 2013.
  * [20] Young Hun Jung, Jack Goetz, and Ambuj Tewari.  Online multiclass boosting.  In Advances in neural information processing systems, pages 919–928, 2017.
  * [21] Young Hun Jung and Ambuj Tewari.  Online boosting algorithms for multi-label ranking.  In International Conference on Artificial Intelligence and Statistics, pages 279–287, 2018.
  * [22] Sham Kakade and John Langford.  Approximately optimal approximate reinforcement learning.  In In Proc. 19th International Conference on Machine Learning. Citeseer, 2002.
  * [23] Varun Kanade and Adam Kalai.  Potential-based agnostic boosting.  In Advances in neural information processing systems, pages 880–888, 2009.
  * [24] Alessandro Lazaric and Rémi Munos.  Hybrid stochastic-adversarial on-line learning.  In Conference on Learning Theory, 2009.
  * [25] 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.
  * [26] Aryan Mokhtari, Hamed Hassani, and Amin Karbasi.  Stochastic conditional gradient methods: From convex minimization to submodular maximization.  arXiv preprint arXiv:1804.09554, 2018.
  * [27] Rémi Munos and Csaba Szepesvári.  Finite-time bounds for fitted value iteration.  Journal of Machine Learning Research, 9(5), 2008.
  * [28] Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari.  Online learning: Stochastic and constrained adversaries.  arXiv preprint arXiv:1104.5070, 2011.
  * [29] Robert E Schapire and Yoav Freund.  Boosting: Foundations and Algorithms.  MIT Press, 2012.
  * [30] 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.
  * [31] 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.
  * [32] Ronald J Williams.  Simple statistical gradient-following algorithms for connectionist reinforcement learning.  Machine learning, 8(3-4):229–256, 1992.
  * [33] Jiahao Xie, Zebang Shen, Chao Zhang, Hui Qian, and Boyu Wang.  Stochastic recursive gradient-based methods for projection-free online learning.  arXiv preprint arXiv:1910.09396, 2019.

##  Appendix A Step-size subroutine

Below we give an algorithm for choosing step sizes used in both of the RL
boosting methods (for online, and supervised, weak learners).

Algorithm 3 $\texttt{StepChooser}(\pi_{t-1},\pi^{\prime}_{t},\mu,P)$

1: Execute $\pi_{t-1}$ for $P$ episodes with initial state distribution $\mu$
via Algorithm 2, to get  $D=\\{(s_{i},\widehat{Q_{i}})_{i=1}^{P}\\}.$

2: For any policy $\pi$, let
$\widehat{G^{\pi}}=\frac{1}{P}\sum_{p=1}^{P}\widehat{Q_{i}}^{\top}\pi(\cdot|s_{i})$.

3: Return
$\eta_{1,t}=\texttt{clip}_{[0,1]}\left(\frac{(1-\gamma)^{2}}{2}\left(\widehat{G^{\pi^{\prime}_{t}}}-\widehat{G^{\pi_{t-1}}}\right)\right)$

##  Appendix B RL Boosting via Weak Online Learning

Algorithm 4 RL Boosting via Weak Online Learning

1: Initialize a policy $\pi_{0}\in\Pi_{W}$ arbitrarily.

2: for $t=1$ to $T$ do

3: Initialize online weak learners ${\mathcal{W}}_{1},\dots\mathcal{W}^{N}$.

4: for $m=1$ to $M$ do

5: Execute $\pi_{t-1}$ once with initial state distribution $\mu$ via
Algorithm 2, to get $(s_{t,m},\widehat{Q}_{t,m})$.

6: Choose $\rho_{t,m,0}\in\Pi_{W}$ arbitrarily.

7: for $n=1$ to $N$ do

8: Set
$\rho_{t,m,n}=(1-\eta_{2,n})\rho_{t,m,n-1}+\frac{\eta_{2,n}}{\alpha}{\mathcal{W}}^{n}-\eta_{2,n}\left(\frac{1}{\alpha}-1\right)\pi_{r}$.

9: end for

10: Pass to each ${\mathcal{W}}^{n}$ the following loss linear $f_{t,m,n}$:
$f_{t,m,n}=-\nabla\mkern-2.5muF_{G,\beta}[-\widehat{Q}_{t,m}](\rho_{t,m,n}(\cdot|s_{i}))$

11: end for

12: Declare
$\pi^{\prime}_{t}=\frac{1}{M}\sum_{m=1}^{M}\Gamma\left[\rho_{t,m,N}\right]$.

13: Choose $\eta_{1,t}=\min\\{1,\frac{2C_{\infty}(\mathbbl{\Pi})}{t}\\}$ if
$\mu=d_{0}$ else set
$\eta_{1,t}=\texttt{StepChooser}(\pi_{t-1},\pi^{\prime}_{t},\mu,P)$.

14: Update $\pi_{t}=(1-\eta_{1,t})\pi_{t-1}+\eta_{1,t}\pi^{\prime}_{t}$.

15: end for

16: Output $\bar{\pi}$= $\pi_{T}$ if $\mu=d_{0}$ else output $\pi_{t-1}$ with
the smallest $\eta_{t}$.

######  Theorem 15.

Algorithm 4 samples $T(M+P)$ episodes of length
$\frac{1}{1-\gamma}\log\frac{T(M+P)}{\delta}$ with probability $1-\delta$. In
the episodic model, Algorithm 4 guarantees as long as
$T=\frac{16C^{2}_{\infty}(\mathbbl{\Pi})}{(1-\gamma)^{3}\varepsilon}$,
$N=\left(\frac{16|A|C_{\infty}(\mathbbl{\Pi})}{(1-\gamma)^{2}\alpha\epsilon}\right)^{2}$,
$M=\max\left\\{\frac{1000|A|^{2}C^{2}_{\infty}(\mathbbl{\Pi})}{(1-\gamma)^{4}\varepsilon^{2}\alpha^{2}}\log^{2}{T}{\delta},\frac{8|A|C_{\infty}(\mathbbl{\Pi})R_{\mathcal{W}}(M)}{(1-\gamma)^{2}\alpha\varepsilon}\right\\}$,$\mu=d_{0}$,
we have with probability $1-\delta$

$V^{*}-V^{\pi}~{}\leq~{}C_{\infty}(\mathbbl{\Pi})\frac{\mathcal{E}(\mathbbl{\Pi},\Pi)}{1-\gamma}+\varepsilon$

In the $\nu$-reset model, Algorithm 1 guarantees as long as
$T=\frac{100D^{2}_{\infty}}{(1-\gamma)^{6}\varepsilon^{2}}$,
$N=\left(\frac{20|A|D_{\infty}}{(1-\gamma)^{3}\alpha\epsilon}\right)^{2}$,
$P=\frac{250D_{\infty}^{2}|A|^{2}}{(1-\gamma)^{6}\varepsilon^{2}}\log^{2}\frac{T}{\delta}$,
$M=\max\left\\{\left(\frac{40|A|D_{\infty}}{(1-\gamma)^{3}\alpha\varepsilon}\log\frac{T}{\delta}\right)^{2},\frac{10|A|D_{\infty}R_{\mathcal{W}}(M)}{(1-\gamma)^{3}\alpha\varepsilon}\right\\}$,$\mu=\nu$,
we have with probability $1-\delta$

$V^{*}-V^{\pi}~{}\leq~{}D_{\infty}\frac{\mathcal{E}_{\nu}(\mathbbl{\Pi},\Pi)}{(1-\gamma)^{2}}+\varepsilon$

If $R_{\mathcal{W}}(M)=\sqrt{M\log|{\mathcal{W}}|}$ for some measure of weak
learning complexity $|{\mathcal{W}}|$, the algorithm samples
$\tilde{O}\left(\frac{C_{\infty}^{4}(\mathbbl{\Pi})|A|^{2}\log|{\mathcal{W}}|}{(1-\gamma)^{7}\alpha^{2}\varepsilon^{3}}\right)$
episodes in the episodic model, and
$\tilde{O}\left(\frac{D_{\infty}^{4}|A|^{2}\log|{\mathcal{W}}|}{(1-\gamma)^{12}\alpha^{2}\varepsilon^{4}}\right)$
in the $\nu$-reset model.

##  Appendix C Non-convex Frank-Wolfe

In this section, 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, adapted to non-convex and gradient
dominated function classes (see Definition 1).

The Frank-Wolfe (FW) method assumes oracle access to a black-box linear
optimizer, denoted $\mathcal{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 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 4.

#### Setting.

Denote by $\mathcal{O}$ a black-box oracle to an
$(\epsilon_{0},\mathcal{K}_{2})$-approximate linear optimizer over a convex
set $\mathcal{K}\subseteq\mathbb{R}^{d}$ such that for any given
$v\in\mathbb{R}^{d}$, we have

$v^{\top}\mathcal{O}(v)~{}\geq~{}\max_{u\in\mathcal{K}_{2}}v^{\top}u-\epsilon_{0}.$

Algorithm 5 Non-convex Frank-Wolfe

1: Input: $T>0$, objective $f$, linear optimization oracle $\mathcal{O}$

2: Choose $x_{0}$ arbitrarily.

3: for $t=1,\ldots,T$ do

4: Call $z_{t}=\mathcal{O}(\nabla\mkern-2.5mu_{t-1})$, where
$\nabla\mkern-2.5mu_{t-1}=\nabla\mkern-2.5muf(x_{t-1})$.

5: Choose $\eta_{t}=\min\\{1,\frac{2\kappa}{t}\\}$ in the gradient-dominated
case, else choose $\eta_{t}$ so that
$|LD^{2}\eta_{t}-\nabla\mkern-2.5mu_{t-1}^{\top}(z_{t}-x_{t-1})|~{}\leq~{}\epsilon.$

6: Set $x_{t}=(1-\eta_{t})x_{t-1}+\eta_{t}z_{t}$.

7: end for

8: return $\bar{x}=x_{T}$ in the gradient-dominated case, else $x_{t-1}$ with
the smallest $\eta_{t}$.

######  Theorem 16.

Let $f:\mathcal{K}\to\mathbb{R}$ be $L$-smooth in some norm $\|\cdot\|_{*}$,
$H$-bounded, and the diameter of $\mathcal{K}$ in $\|\cdot\|_{*}$ be $D$.
Then, for a $(\epsilon_{0},\mathcal{K}_{2})$-linear optimization oracle, the
output $\bar{x}$ of Algorithm 5 satisfies

$\max_{u\in\mathcal{K}_{2}}\nabla\mkern-2.5muf(\bar{x})^{\top}(u-\bar{x})~{}\leq~{}\sqrt{\frac{2HLD^{2}}{T}}+3\epsilon+\epsilon_{0}.$

Furthermore, if $f$ is $(\kappa,\tau,\mathcal{K}_{1},\mathcal{K}_{2})$-locally
gradient-dominated and $x_{0},\dots x_{T}\in\mathcal{K}_{1}$, then it holds

$\max_{x^{*}\in\mathcal{K}}f(x^{*})-f(\bar{x})~{}\leq~{}\frac{2\kappa^{2}\max\\{LD^{2},H\\}}{T}+\tau+\kappa\epsilon_{0}.$

##  Appendix D Analysis for Boosting with Supervised Learning (Proof of
Theorem 12)

###### Proof of Theorem 12.

The broad scheme here is to utilize an equivalence between Algorithm 1 and
Algorithm 5 on the function $V^{\pi}$ (or $V^{\pi}_{\nu}$ in the $\nu$-reset
model), to which Theorem 16 applies.

To this end, firstly, note $V^{\pi}$ is $\frac{1}{1-\gamma}$-bounded. Define a
norm $\|\cdot\|_{\infty,1}:\mathbb{R}^{|S|\times|A|}\to\mathbb{R}$ as
$\|x\|_{1,\infty}=\max_{s\in S}\sum_{a\in A}|x_{s,a}|$. Further, observe that
for any policy $\pi:S\to\Delta_{A}$, $\|\pi\|_{\infty,1}=1$. The following
lemma specifies the smoothness of $V^{\pi}$ in this norm.

######  Lemma 17.

$V^{\pi}$ is $\frac{2\gamma}{(1-\gamma)^{3}}$-smooth in the
$\|\cdot\|_{\infty,1}$ norm.

To be able to interpret Algorithm 1 as an instantiation of the algorithmic
template Algorithm 5 presents, we advance two claims: one, the step-size
choices of the two algorithms conincide; two, $\pi^{\prime}_{t}$ (Line 3-10)
serves as an approximate linear optimizers for
$\nabla\mkern-2.5muV^{\pi_{t-1}}$. Together, these imply that the iterates
produced by the two algorithms conincide. The first of these, which provides a
value of $\epsilon$ to use in the statement of Theorem 16, is established
below.

######  Claim 18.

Upon every invocation of StepChooser, the output $\eta_{1,t}$ satisfies with
probability $1-\delta$

$\left|\frac{2\eta_{1,t}}{(1-\gamma)^{3}}-(\nabla\mkern-2.5muV_{\mu}^{\pi_{t-1}})^{\top}(\pi^{\prime}_{t}-\pi_{t-1})\right|~{}\leq~{}\frac{16|A|}{(1-\gamma)^{2}\sqrt{P}}\log\frac{1}{\delta}$

Next, we move onto the linear optimization equivalence. Indeed, Claim 19
demonstrates that $\pi^{\prime}_{t}$ serves a linear optimizer over gradients
of the function $V^{\pi}$; the suboptimality specifies $\epsilon_{0}$.

######  Claim 19.

Let $\beta=\sqrt{\frac{1}{\alpha N}}$, and
$\eta_{2,n}=\min\\{\frac{2}{n},1\\}$. Then, for any $t$, $\pi^{\prime}_{t}$
produced by Algorithm 1 satisfies with probability $1-\delta$

$\max_{\pi\in\Pi}(\nabla\mkern-2.5muV^{\pi_{t-1}}_{\mu})^{\top}(\pi-\pi^{\prime}_{t})~{}\leq~{}\frac{2|A|}{(1-\gamma)^{2}\alpha}\left(\frac{2}{\sqrt{N}}+\varepsilon_{W}\right)$

Finally, observe that it is by construction that $\pi_{t}\in\mathbbl{\Pi}$.
Therefore, in terms of the previous section, $\mathcal{K}$ is the class of all
policies, $\mathcal{K}_{1}=\mathbbl{\Pi}$, $\mathcal{K}_{2}=\Pi$.

In the episodic model, we wish to invoke the second part of Theorem 16. The
next lemma establishes gradient-domination properties of $V^{\pi}$ to support
this.

######  Lemma 20.

$V^{\pi}$ is
$\left(C_{\infty}(\mathbbl{\Pi}),\frac{1}{1-\gamma}C_{\infty}(\mathbbl{\Pi})\mathcal{E}(\Pi,\mathbbl{\Pi}),\mathbbl{\Pi},\Pi\right)$-gradient
dominated, i.e. for any $\pi\in\mathbbl{\Pi}$:

$V^{*}-V^{\pi}~{}\leq~{}C_{\infty}(\mathbbl{\Pi})\left(\frac{1}{1-\gamma}\mathcal{E}(\Pi,\mathbbl{\Pi})+\max_{\pi^{\prime}\in\Pi}(\nabla\mkern-2.5muV^{\pi})^{\top}(\pi^{\prime}-\pi)\right)$

Deriving $\kappa,\tau$ from the above lemma along with $\epsilon_{0}$ from
Claim 19 and $\epsilon$ from Claim 18, as a consequence of the second part of
Theorem 16, we have with probability $1-NT\delta$

$\displaystyle
V^{*}-V^{\bar{\pi}}~{}\leq~{}C_{\infty}(\mathbbl{\Pi})\frac{\mathcal{E}(\mathbbl{\Pi},\Pi)}{1-\gamma}+\frac{4C^{2}_{\infty}(\mathbbl{\Pi})}{(1-\gamma)^{3}T}+\frac{4|A|C_{\infty}(\mathbbl{\Pi})}{(1-\gamma)^{2}\alpha\sqrt{N}}+\frac{2|A|C_{\infty}(\mathbbl{\Pi})}{(1-\gamma)^{2}\alpha}\varepsilon_{W}.$

Similarly, in the $\nu$-reset model, the first part of Theorem 16 provides a
local-optimality guarantee for $V^{\pi}_{\nu}$. Lemma 21 provides a bound on
the function-value gap (on $V^{\pi}$) provided such local-optimality
conditions.

######  Lemma 21.

For any $\pi\in\mathbbl{\Pi}$, we have

$V^{*}-V^{\pi}~{}\leq~{}\frac{1}{1-\gamma}D_{\infty}\left(\frac{1}{1-\gamma}\mathcal{E}_{\nu}(\Pi,\mathbbl{\Pi})+\max_{\pi^{\prime}\in\Pi}(\nabla\mkern-2.5muV_{\nu}^{\pi})^{\top}(\pi^{\prime}-\pi)\right)$

Again, using the bound on
$\max_{\pi^{\prime}\in\Pi}(\nabla\mkern-2.5muV_{\nu}^{\bar{\pi}})^{\top}(\pi^{\prime}-\bar{\pi})$
Theorem 16 provides, we have that with probability $1-2NT\delta$

$\displaystyle
V^{*}-V^{\bar{\pi}}~{}\leq~{}\frac{D_{\infty}\mathcal{E}_{\nu}(\mathbbl{\Pi},\Pi)}{(1-\gamma)^{2}}+\frac{2D_{\infty}}{(1-\gamma)^{3}\sqrt{T}}+\frac{2|A|D_{\infty}}{(1-\gamma)^{3}\alpha}\left(\frac{2}{\sqrt{N}}+\varepsilon_{W}\right)+\frac{48|A|D_{\infty}}{(1-\gamma)^{3}\sqrt{P}}\log\frac{1}{\delta}$

∎

##  Appendix E Analysis for Boosting with Online Learning (Proof of Theorem
15)

###### Proof of Theorem 15.

Similar to the proof of Theorem 12, we establish an equivalence between
Algorithm 1 and Algorithm 5 on the function $V^{\pi}$ (or $V^{\pi}_{\nu}$ in
the $\nu$-reset model), to which Theorem 16 applies provided smoothness (see
Lemma 17).

Indeed, Claim 22 demonstrates $\pi^{\prime}_{t}$ serves a linear optimizer
over gradients of the function $V^{\pi}$, and provides a bound on
$\epsilon_{0}$. Claim 18 ensures that that the step size choices (and hence
iterates) of the two algorithms coincide. As before, observe that it is by
construction that $\pi_{t}\in\mathbbl{\Pi}$.

######  Claim 22.

Let $\beta=\sqrt{\frac{1}{\alpha N}}$, and
$\eta_{2,n}=\min\\{\frac{2}{n},1\\}$. Then, for any $t$, $\pi^{\prime}_{t}$
produced by Algorithm 4 satisfies with probability $1-\delta$

$\max_{\pi\in\Pi}(\nabla\mkern-2.5muV^{\pi_{t-1}}_{\mu})^{\top}(\pi-\pi^{\prime}_{t})~{}\leq~{}\frac{2|A|}{(1-\gamma)^{2}\alpha}\left(\frac{2}{\sqrt{N}}+\frac{R_{\mathcal{W}}(M)}{M}+\sqrt{\frac{16\log\delta^{-1}}{M}}\right)$

In the episodic model, one may combine the second part of Theorem 16, which
provides a bound on function-value gap for gradient dominated functions, which
Lemma 20 guarantees, to conclude with probability $1-T\delta$

$\displaystyle
V^{*}-V^{\bar{\pi}}~{}\leq~{}\frac{C_{\infty}(\mathbbl{\Pi})\mathcal{E}(\mathbbl{\Pi},\Pi)}{1-\gamma}+\frac{4C^{2}_{\infty}(\mathbbl{\Pi})}{(1-\gamma)^{3}T}+\frac{4|A|C_{\infty}(\mathbbl{\Pi})}{(1-\gamma)^{2}\alpha\sqrt{N}}+\frac{2|A|C_{\infty}(\mathbbl{\Pi})}{(1-\gamma)^{2}\alpha}\frac{R_{\mathcal{W}}(M)}{M}+\frac{8|A|C_{\infty}(\mathbbl{\Pi})\log\delta^{-1}}{(1-\gamma)^{2}\alpha\sqrt{M}}.$

Similarly, in the $\nu$-reset model, Lemma 21 provides a bound on the
function-value gap provided local-optimality conditions, which the first part
of Theorem 16 provides for. Again, with probability $1-T\delta$

$\displaystyle
V^{*}-V^{\bar{\pi}}~{}\leq~{}\frac{D_{\infty}\mathcal{E}_{\nu}(\mathbbl{\Pi},\Pi)}{(1-\gamma)^{2}}+\frac{2D_{\infty}}{(1-\gamma)^{3}}\left(\frac{1}{\sqrt{T}}+\frac{|A|}{\alpha}\left(\frac{2}{\sqrt{N}}+\frac{R_{\mathcal{W}}(M)}{M}+\frac{4\log\delta^{-1}}{\sqrt{M}}\right)+\frac{24|A|}{\sqrt{P}}\log\frac{1}{\delta}\right)$

∎

##  Appendix F Proofs of Supporting Claims

###  F.1 Non-convex Frank-Wolfe method (Theorem 16)

###### Proof of Theorem 16.

Non-convex case. Note that for any timestep $t$, it holds due to smoothness
that

$\displaystyle f(x_{t})$ $\displaystyle=f(x_{t-1}+\eta_{t}({z_{t}}-x_{t-1}))$
$\displaystyle~{}\geq~{}f(x_{t-1})+\eta_{t}\nabla\mkern-2.5mu_{t-1}^{\top}(z_{t}-x_{t-1})-\eta_{t}^{2}\frac{L}{2}D^{2}$
$\displaystyle=f(x_{t-1})-\frac{1}{2LD^{2}}\left(LD^{2}\eta_{t}-\nabla\mkern-2.5mu_{t-1}^{\top}(z_{t}-x_{t-1})\right)^{2}+\frac{(\nabla\mkern-2.5mu_{t-1}^{\top}(z_{t}-x_{t-1}))^{2}}{2LD^{2}}$

Using the step-size definition to bound on the middle term, and telescoping
this inequality over function-value differences across successive iterates, we
have

$\displaystyle\min_{t}(\nabla\mkern-2.5mu_{t-1}^{\top}(z_{t}-x_{t-1}))^{2}~{}\leq~{}\frac{1}{T}\sum_{t=1}^{T}(\nabla\mkern-2.5mu_{t-1}^{\top}(z_{t}-x_{t-1}))^{2}~{}\leq~{}\frac{2LD^{2}H}{T}+\epsilon^{2}$

Let $t^{\prime}=\operatorname*{arg\,min}_{t}\eta_{t}$ and
$t^{*}=\operatorname*{arg\,min}_{t}(\nabla\mkern-2.5mu_{t-1}^{\top}(z_{t}-x_{t-1}))^{2}$.
Then

$\displaystyle\nabla\mkern-2.5mu_{t^{\prime}-1}^{\top}(z_{t^{\prime}}-x_{t^{\prime}-1})$
$\displaystyle~{}\leq~{}LD^{2}\eta_{t^{\prime}}+\epsilon~{}\leq~{}LD^{2}\eta_{t^{*}}+\epsilon$
$\displaystyle~{}\leq~{}\nabla\mkern-2.5mu_{t^{*}-1}^{\top}(z_{t^{*}}-x_{t^{*}-1})+2\epsilon~{}\leq~{}\sqrt{\frac{2LD^{2}H}{T}+\epsilon^{2}}+2\epsilon$

To conclude the claim for the non-convex part, observe
$\sqrt{a+b}~{}\leq~{}\sqrt{a}+\sqrt{b}$ for $a,b>0$, and that since
$z_{t^{\prime}}=\mathcal{O}(\nabla\mkern-2.5mu_{t^{\prime}-1})$, it follows by
oracle definition that

$\max_{u\in\mathcal{K}_{2}}\nabla\mkern-2.5mu_{t^{\prime}-1}^{\top}u~{}\leq~{}\nabla\mkern-2.5mu_{t^{\prime}-1}^{\top}z_{t^{\prime}}+\epsilon_{0}.$

#### Gradient-Dominated Case.

Define $x^{*}=\operatorname*{arg\,max}_{x\in\mathcal{K}}f(x)$ and
$h_{t}=f(x^{*})-f(x_{t})$.

$\displaystyle h_{t}$
$\displaystyle~{}\leq~{}h_{t-1}-\eta_{t}\nabla\mkern-2.5mu_{t-1}^{\top}(z_{t}-x_{t-1})+\eta_{t}^{2}\frac{L}{2}D^{2}$
smoothness
$\displaystyle~{}\leq~{}h_{t-1}-\eta_{t}\max_{y\in\mathcal{K}_{2}}\eta_{t}\nabla\mkern-2.5mu_{t-1}^{\top}(y-x_{t-1})+\eta_{t}^{2}\frac{L}{2}D^{2}+\eta_{t}\epsilon_{0}$
oracle
$\displaystyle~{}\leq~{}h_{t-1}-\frac{\eta_{t}}{\kappa}(f(x^{*})-f(x_{t-1}))+\eta_{t}^{2}\frac{L}{2}D^{2}+\eta_{t}\left(\epsilon_{0}+\frac{\tau}{\kappa}\right)$
gradient domination
$\displaystyle=\left(1-\frac{\eta_{t}}{\kappa}\right)h_{t-1}+\eta_{t}^{2}\frac{L}{2}D^{2}+\eta_{t}\left(\epsilon_{0}+\frac{\tau}{\kappa}\right)$

The theorem now follows from the following claim.

######  Claim 23.

Let $C~{}\geq~{}1$. Let $g_{t}$ be a $H$-bounded positive sequence such that

$g_{t}~{}\leq~{}\left(1-\frac{\sigma_{t}}{C}\right)g_{t-1}+\sigma_{t}^{2}D+\sigma_{t}E.$

Then choosing $\sigma_{t}=\min\\{1,\frac{2C}{t}\\}$ implies
$g_{t}~{}\leq~{}\frac{2C^{2}\max\\{2D,H\\}}{t}+CE$.

∎

###  F.2 Smoothness of value function (Lemma 17)

###### Proof of Lemma 17.

Consider any two policies $\pi,\pi^{\prime}$. Using the Performance Difference
Lemma (Lemma 3.2 in [2], e.g.) and Equation 2, we have

$\displaystyle|V^{\pi^{\prime}}-V^{\pi}-\nabla\mkern-2.5muV^{\pi}(\pi^{\prime}-\pi)|$
$\displaystyle=$ $\displaystyle\frac{1}{1-\gamma}\left|{\mathbb E}_{s\sim
d^{\pi^{\prime}}}\left[Q^{\pi}(\cdot|s)^{\top}(\pi^{\prime}(\cdot|s)-\pi(\cdot|s)\right]-{\mathbb
E}_{s\sim
d^{\pi}}\left[Q^{\pi}(\cdot|s)^{\top}(\pi^{\prime}(\cdot|s)-\pi(\cdot|s)\right]\right|$
$\displaystyle~{}\leq~{}$
$\displaystyle\frac{1}{(1-\gamma)^{2}}\|d^{\pi^{\prime}}-d^{\pi}\|_{1}\|\pi^{\prime}-\pi\|_{\infty,1}$

The last inequality uses the fact that
$\max_{s,a}Q^{\pi}(s,a)~{}\leq~{}\frac{1}{1-\gamma}$. It suffices to show
$\|d^{\pi^{\prime}}-d^{\pi}\|_{1}~{}\leq~{}\frac{\gamma}{1-\gamma}\|\pi^{\prime}-\pi\|_{\infty,1}$.
To establish this, consider the Markov operator
$P^{\pi}(s^{\prime}|s)=\sum_{a\in A}P(s^{\prime}|s,a)\pi(a|s)$ induced by a
policy $\pi$ on MDP $M$. For any distribution $d$ supported on $S$, we have

$\displaystyle\|(P^{\pi^{\prime}}-P^{\pi})d\|_{1}$
$\displaystyle=\sum_{s^{\prime}}\left|\sum_{s,a}P(s^{\prime}|s,a)d(s)(\pi^{\prime}(a|s)-\pi(a|s)\right|$
$\displaystyle~{}\leq~{}\sum_{s^{\prime}}P(s^{\prime}|s,a)\|d\|_{1}\|\pi^{\prime}-\pi\|_{\infty,1}~{}\leq~{}\|\pi^{\prime}-\pi\|_{\infty,1}$

Using sub-additivity of the $l_{1}$ norm and applying the above observation
$t$ times, we have for any $t$

$\|((P^{\pi^{\prime}})^{t}-(P^{\pi})^{t})d\|_{1}~{}\leq~{}t\|\pi^{\prime}-\pi\|_{\infty,1}.$

Finally, observe that

$\displaystyle\|d^{\pi^{\prime}}-d^{\pi}\|_{1}$
$\displaystyle~{}\leq~{}(1-\gamma)\sum_{t=0}^{\infty}\gamma^{t}\|((P^{\pi^{\prime}})^{t}-(P^{\pi})^{t})d_{0}\|_{1}$
$\displaystyle~{}\leq~{}\|\pi^{\prime}-\pi\|_{\infty,1}(1-\gamma)\sum_{t=0}^{\infty}t\gamma^{t}=\frac{\gamma}{1-\gamma}\|\pi^{\prime}-\pi\|_{\infty,1}$

∎

###  F.3 Step-size guarantee (Claim 18)

###### Proof of Claim 18.

Let $\mathcal{D}$ be the distribution induced by Algorithm 2 upon being given
$\pi_{t-1}$. Due to Lemma 14, it suffices to demonstrate that for any
$\pi\in\\{\pi^{\prime}_{t},\pi_{t-1}\\}$ the following claim holds with
probability $1-\frac{\delta}{2}$. The claim in turn follows from Hoeffding’s
inequality, while noting $\widehat{Q^{\pi_{t-1}}}(s,\cdot)$ is
$\frac{|A|}{1-\gamma}$-bounded in the $l_{\infty}$ norm.

$\left|\widehat{G^{\pi}}-{\mathbb
E}_{(s,\widehat{Q^{\pi_{t-1}}}(s,\cdot))\sim\mathcal{D}}\Big{[}\widehat{Q^{\pi_{t-1}}}(s,\cdot)^{\top}\pi(\cdot|s)\Big{]}\right|~{}\leq~{}\frac{8|A|}{(1-\gamma)\sqrt{P}}\log\frac{1}{2\delta}$

∎

###  F.4 Gradient domination (Lemma 20 and Lemma 21)

###### Proof of Lemma 20.

Invoking Lemma 4.1 from [2] with $\mu=d_{0}$, we have

$\displaystyle V^{*}-V^{\pi}$
$\displaystyle~{}\leq~{}\left\|\frac{d^{\pi^{*}}}{d^{\pi}}\right\|_{\infty}\max_{\pi_{0}}(\nabla\mkern-2.5muV^{\pi})^{\top}(\pi_{0}-\pi)$
$\displaystyle~{}\leq~{}C_{\infty}(\mathbbl{\Pi})(\max_{\pi_{0}}(\nabla\mkern-2.5muV^{\pi})^{\top}\pi_{0}-\max_{\pi^{\prime}\in\Pi}(\nabla\mkern-2.5muV^{\pi})^{\top}\pi^{\prime}+\max_{\pi^{\prime}\in\Pi}(\nabla\mkern-2.5muV^{\pi})^{\top}(\pi^{\prime}-\pi))$

Finally, with the aid of Equation 2, observe that

$\displaystyle\max_{\pi_{0}}(\nabla\mkern-2.5muV^{\pi})^{\top}\pi_{0}-\max_{\pi^{\prime}\in\Pi}(\nabla\mkern-2.5muV^{\pi})^{\top}\pi^{\prime}$
$\displaystyle=\min_{\pi^{\prime}\in\Pi}\frac{1}{1-\gamma}{\mathbb E}_{s\sim
d^{\pi}}\left[\max_{a}Q^{\pi}(s,a)-Q^{\pi}(\cdot|s)^{\top}\pi^{\prime}\right]$
$\displaystyle~{}\leq~{}\frac{1}{1-\gamma}\mathcal{E}(\Pi,\mathbbl{\Pi})$

∎

###### Proof of Lemma 21.

Invoking Lemma 4.1 from [2] with $\mu=\nu$, we have

$\displaystyle V^{*}-V^{\pi}$
$\displaystyle~{}\leq~{}\frac{1}{1-\gamma}\left\|\frac{d^{\pi^{*}}}{\nu}\right\|_{\infty}\max_{\pi_{0}}(\nabla\mkern-2.5muV_{\nu}^{\pi})^{\top}(\pi_{0}-\pi)$
$\displaystyle~{}\leq~{}\frac{1}{1-\gamma}D_{\infty}(\max_{\pi_{0}}(\nabla\mkern-2.5muV_{\nu}^{\pi})^{\top}\pi_{0}-\max_{\pi^{\prime}\in\Pi}(\nabla\mkern-2.5muV_{\nu}^{\pi})^{\top}\pi^{\prime}+\max_{\pi^{\prime}\in\Pi}(\nabla\mkern-2.5muV_{\nu}^{\pi})^{\top}(\pi^{\prime}-\pi))$

Again, with the aid of Equation 2, observe that

$\displaystyle\max_{\pi_{0}}(\nabla\mkern-2.5muV_{\nu}^{\pi})^{\top}\pi_{0}-\max_{\pi^{\prime}\in\Pi}(\nabla\mkern-2.5muV_{\nu}^{\pi})^{\top}\pi^{\prime}$
$\displaystyle=\min_{\pi^{\prime}\in\Pi}\frac{1}{1-\gamma}{\mathbb E}_{s\sim
d_{\nu}^{\pi}}\left[\max_{a}Q^{\pi}(s,a)-Q^{\pi}(\cdot|s)^{\top}\pi^{\prime}\right]$
$\displaystyle~{}\leq~{}\frac{1}{1-\gamma}\mathcal{E}_{\nu}(\Pi,\mathbbl{\Pi})$

∎

###  F.5 Supervised linear optimization guarantees (Claim 19)

###### Proof of Claim 19.

The subroutine presented in lines 3-10 (which culminate in $\pi^{\prime}_{t}$)
is an instantiation of Algorithm 3 from [18], specializing the decision set to
be $\Delta_{A}$. To note the equivalence, note that in [18] the algorithm is
stated assuming that the center-of-mass of the decision set is at the origin
(after a coordinate transform); correspondingly, the update rule in Algorithm
1 can be written as

$(\rho_{t,n}-\pi_{r})=(1-\eta_{2,n})(\rho_{t,n-1}-\pi_{r})+\frac{\eta_{2,n}}{\alpha}(\mathcal{A}_{t,n}-\pi_{r}).$

For any state $s$, $\pi_{r}(\cdot|s)=\frac{1}{A}\mathbf{1}_{|A|}$ corresponds
to the center-of-masss of $\Delta_{A}$. Finally, note that maximizing
$f^{\top}x$ over $x\in\mathcal{K}$ is equivalent to minimizing $(-f)^{\top}x$
over the same domain. Therefore, we can borrow the following result on
boosting for statistical learning from [18] (Theorem 13). Note that
$\widehat{Q^{\pi}}(s,\cdot)$ produced by Algorithm 2 satisfies
$\|\widehat{Q^{\pi}}(s,\cdot)\|=\frac{|A|}{1-\gamma}$. Let $\mathcal{D}_{t}$
be the distribution induced by the trajectory sampler in round $t$.

######  Theorem 24 ([18]).

Let $\beta=\sqrt{\frac{1}{\alpha N}}$, and
$\eta_{2,n}=\min\\{\frac{2}{n},1\\}$. Then, for any $t$, $\pi^{\prime}_{t}$
produced by Algorithm 1 satisfies with probability $1-\delta$ that

$\max_{\pi\in\Pi}\mathbb{E}_{(s,Q)\sim\mathcal{D}_{t}}\left[Q^{\top}\pi(s)\right]-\mathbb{E}_{(s,Q)\sim\mathcal{D}_{t}}\left[Q^{\top}\pi^{\prime}_{t}(s)\right]~{}\leq~{}\frac{2|A|}{(1-\gamma)\alpha}\left(\frac{2}{\sqrt{N}}+\varepsilon\right)$

Lemma 14 allows us to restate the guarantees in the previous subsection in
terms of linear optimization over functional gradients. The conclusion thus
follows immediately by combining Lemma 14 and Theorem 24. ∎

###  F.6 Online linear optimization guarantees (Claim 22)

###### Proof of Claim 22.

In a similar vein to the proof of Claim 19, here we state the a result on
boosting for online convex optimization (OCO) from [18] (Theorem 6), the
counterpart of Theorem 13 for the online weak learning case.

######  Theorem 25 ([18]).

Let $\beta=\sqrt{\frac{1}{\alpha N}}$, and
$\eta_{2,n}=\min\\{\frac{2}{n},1\\}$. Then, for any $t$,
$\Gamma[\rho_{t,m,N}]$ produced by Algorithm 4 satisfies

$\max_{\pi\in\Pi}\sum_{m=1}^{M}\left[\hat{Q}_{t,m}^{\top}\pi(s_{t,m})\right]-\sum_{m=1}^{M}\left[\hat{Q}_{t,m}^{\top}\Gamma[\rho_{t,m,N}](s_{t,m})\right]~{}\leq~{}\frac{2|A|}{(1-\gamma)\alpha}\left(\frac{2M}{\sqrt{N}}+R_{\mathcal{W}}(M)\right)$

Next we invoke online-to-batch conversions. Note that in Algorithm 4,
$(s_{t,m},\hat{Q}_{t,m})$ for any fixed $t$ is sampled i.i.d. from the same
distribution. Therefore, we can apply online-to-batch results, i.e. Theorem
9.5 in [16], on Theorem 25 to get

$\max_{\pi\in\Pi}\mathbb{E}_{(s,Q)\sim\mathcal{D}_{t}}\left[Q^{\top}\pi(s)\right]-\mathbb{E}_{(s,Q)\sim\mathcal{D}_{t}}\left[Q^{\top}\pi^{\prime}_{t}(s)\right]~{}\leq~{}\frac{2|A|}{(1-\gamma)\alpha}\left(\frac{2}{\sqrt{N}}+\frac{R_{\mathcal{W}}(M)}{M}+\sqrt{\frac{16\log\delta^{-1}}{M}}\right)$

We finally invoke Lemma 14. ∎

###  F.7 Remaining proofs (Claim 23)

###### Proof of Claim 23.

Let $T^{*}=\operatorname*{arg\,max}_{t}\\{t:t~{}\leq~{}2C\\}$. For any
$t~{}\leq~{}T^{*}$, we have $\sigma_{t}=1$ and
$g_{t}~{}\leq~{}H~{}\leq~{}\frac{2C^{2}H}{t}$. For $t~{}\geq~{}T^{*}$, we
proceed by induction. The base case ($t=T^{*}$) is true by the previous
display. Now, assume $g_{t-1}~{}\leq~{}\frac{2C^{2}\max\\{2D,H\\}}{t-1}+CE$
for some $t>T^{*}$.

$\displaystyle g_{t}$
$\displaystyle~{}\leq~{}\left(1-\frac{2}{t}\right)\left(\frac{2C^{2}\max\\{2D,H\\}}{t-1}+CE\right)+\frac{4C^{2}D}{t^{2}}+\frac{2CE}{t}$
$\displaystyle~{}\leq~{}CE+2C^{2}\max\\{2D,H\\}\left(\frac{1}{t-1}\left(1-\frac{2}{t}\right)+\frac{1}{t^{2}}\right)$
$\displaystyle=CE+2C^{2}\max\\{2D,H\\}\frac{t^{2}-2t+t-1}{t^{2}(t-1)}$
$\displaystyle~{}\leq~{}CE+2C^{2}\max\\{2D,H\\}\frac{t(t-1)}{t^{2}(t-1)}$

∎


# User’s Reaction Patterns in Online Social Network Communities

ABAzza Bouleimen  NPNicolò Pagan  SCStefano Cresci  AUAleksandra Urman
GNGianluca Nogara  SGSilvia Giordano  Department of Innovative Technologies,
University of Applied Sciences and Arts of Southern Switzerland (DTI, SUPSI),
Lugano, CH  Institute of Informatics, University of Zurich (IfI, UZH), Zürich,
CH  Institute for Informatics and Telematics, National Research Council (IIT,
CNR), Pisa, Italy

Research

## Introduction

Misinformation, hate speech, toxicity, trolling, and malicious bots are
examples of undesired behavior on Online Social Networks (OSNs) with the
potential for serious implications in real life for individuals and societies.
These harmful impacts range from escalating physical violence in protests [1],
threatening democratic elections’ integrity [2], to leading to genocides [3].
To address these harms, OSNs platforms introduced some moderation strategies
that aim at mitigating these problems. Most of these interventions follow a
one-size-fits-all approach, as policies are equally applied to all users [4].
However, these interventions sometimes exacerbate the phenomena instead of
limiting them [5, 6]. A possible explanation could consist in the fact that
users present diversified reactions to moderation policies [7], in particular
because users are typically grouped in communities within OSNs. In this
context, some studies highlight the need for personalized moderation
interventions [4]. However, to do so, we need to better understand user’s
susceptibility defined as the factors that drive them toward particular
reactions. In other words, we aim to get insights on what makes users more or
less likely to engage in undesired behavior. In this work, we aim at studying
the reaction of users in network communities as a first step toward
understanding user’s susceptibilities on the individual level. In turn, this
represents a preliminary step towards designing personalized moderation
strategies.

## Results

Dataset. We base our study on the VaccinItaly dataset [8]. It is a collection
of tweets related to the Covid-19 discussion in Italy ranging from Dec, 20th,
2020 to Oct, 22nd 2021. The topic has been very controversial all around the
world. Consequently, the choice of this dataset is suitable for studying the
susceptibilities of users in contexts that prompt adversarial reactions. The
dataset consists of $\sim$12 million tweets in Italian, half of which are
retweets. It involves 551,816 unique users, where 86% of them have less than
20 tweets in the dataset. We selected a subset of users that are involved
enough to reflect the core discussion on the Covid-19 vaccines in Italy. To do
so, we adapted and applied the definition of a core user from [6] to our
dataset. This reduces the number of users to 9,278 (1.7% of users) who are
responsible for nearly half of the tweets.

The purpose of the study being to observe the behavior of users within the
network structure they are in, we built the retweet network of users. It is a
directed weighted network where nodes represent the users and edges represent
retweets. The weights of the edges represent the number of retweets from one
user to another.

Community detection. We applied the Louvain community detection algorithm [9]
on the network with a resolution parameter of 0.7. We obtained two main
communities that gather 87% of the nodes in the network. We qualitatively
analyzed the tweets of the nodes with the high authority scores in these two
communities [10]. In one community, the nodes with high authority scores tweet
content in favor of the vaccines while, in the other community, the nodes with
high authority scores are against the adoption of vaccines and the
government’s measures to contain the spread of the virus. The same
observations are found when analyzing the most retweeted tweets or the tweets
of the most central users in these two communities. Hence, we assume that one
community is dominated by a Pro vaccination discourse (Provax community: 3,980
nodes) and the other is dominated by an Anti vaccination discourse (Novax
community: 3,831 nodes).

Since our work aims at measuring the differences in the reactions of users
belonging to different communities, we first need to understand whether the
communities were stable over time, or whether they evolved. In the latter
case, differences between the two communities could be simply due to the flow
of users between them. To do so, we ran different instances of the community
detection algorithm on different sub-periods of time and evaluated the user’s
flows across communities. Our analysis showed that the composition of the two
communities remains overall stable over time, hence we can use the community
partitioning based on the whole dataset.

Toxicity in communities. In this abstract, due to space restrictions, we limit
the analysis to measuring the user toxicity. Nevertheless, an analysis of
negativity was also done and similar observations were obtained. To measure
the toxicity of the text of the tweet, we used the Detoxify library [11]. It
is a state-of-the-art method for computing toxicity [12, 13]. Detoxify has a
multilingual model for non-English texts. For Italian it reaches an AUC of
89.18% [11]. The model returns a score ranging from 0 (low toxicity) to 1
(high toxicity).

We present in Fig. 1 the daily average toxicity of the text written by the
users belonging to the Provax and Novax communities. Fig. 1 shows that, from
the beginning of the data collection until mid-June, the toxicity level of the
Provax community is lower than the one of the Novax community. Interestingly,
this trend is inverted starting from mid-June where we notice that Provax
users become on average more toxic than Novax users. Overall, the toxicity of
both communities increases throughout time as shown by the Mann-Kendall test
for trends. However, the Provax toxicity rate increases more than twice as
fast as the Novax one.

Figure 1: Daily toxicity average in written text for Provax and Novax
communities. A moving average of a 7-day window was applied to the plot.

Toxicity around specific events. To deepen the analysis, we look into the
reaction of the Provax and Novax communities around specific events related to
the Covid-19 pandemic in Italy. The selected events are presented in Tab. 1.

Table 1: List of event related to the Covid-19 pandemic in Italy. Events highlighted in bold correspond to pics in the number of tweets posted by the user on that day. Date | Event
---|---
Dec. 27th, 2020 | Start of the vaccination campaign in Italy.
Mar. 15th, 2021 | The Italian government announces lockdown during eater vocation.
Apr. 22nd, 2021 | Introducing the use of the Green Pass.
Jun. 11th, 2021 | Death of a young woman after receiving Astrazeneca shot.
Jul. 23rd, 2021 | Announcing mandatory Green Pass starting from the 6th of August 2021.
Aug. 6th, 2021 | Mandatory Green Pass required to access several public spaces.

In Fig. 2, we present box plots of the toxicity of the tweets posted by the
users of the two communities for the three days following a specific event.
Both Provax and Novax have a similar reaction, in terms of toxicity, to the
start of the vaccination campaign on Dec 27th. In fact, there is no
significant difference between the toxicity of the two communities. For Mar.
15th and Apr. 22nd, the toxicity of the Novax community is significantly
higher. This relates to the trends of toxicity observed in Fig. 1. For Jun.
11th, the difference between the two communities is not significant anymore.
This happens at the time where, in Fig. 1, we recognize an increase in the
toxicity level of the Provax community reaching the level of the Novax one.
For Jul. 22nd and Aug. 6th, it is the Provax that is this time significantly
more toxic than the Novax community. Fig. 2 illustrates that users belonging
to different communities develop different reaction patterns depending on
which events they are confronted with. It also supports the inversion in the
temporal trend of the toxicity within both communities observed in Fig. 1.
This result shows that some events might trigger among groups of users a
reaction that can shape the behavior of a whole community, while the impact
can be non-existent for other groups of users. This supports the need for
intervention strategies targeted at the group and at the individual level.

Figure 2: Box plots of the toxicity of tweets published by users of the Provax
and Novax communities three days starting from the event date. The stars under
the event date on the x-axis represent the significance of the difference
between the two communities.

## Conclusion

Through the case study of the VaccinItaly dataset, we studied the reaction of
users to specific events on OSNs considering their position in the network. We
found that these events impact differently the OSN users. They can
significantly alter the behavior of a community as a whole and invert the
dynamics of behavior within the whole network. Our work highlights the
presence of an understudied phenomenon which is the user’s susceptibility to
undesired behavior. It stresses out the importance of understanding the
reasons behind the changes in users’ reactions and fine-tuning the research to
the individual’s level. Possible paths forward include investigating social
contagion effects, the interplay between the reactions in the two communities,
and the existence of a relation between the structure of the network, the
position of a user within the graph, and their reaction to a particular event.
We hope, through our contribution, to pave the way towards building better
OSNs’ intervention strategies centered on the user.

## References

  * [1] Gallacher, J.D., Heerdink, M.W., Hewstone, M.: Online engagement between opposing political protest groups via social media is linked to physical violence of offline encounters. Social Media+ Society 7(1), 2056305120984445 (2021)
  * [2] Luceri, L., Deb, A., Giordano, S., Ferrara, E.: Evolution of bot and human behavior during elections. First Monday (2019)
  * [3] Yue, N.: The” weaponization” of facebook in myanmar: A case for corporate criminal liability. Hastings LJ 71, 813 (2019)
  * [4] Cresci, S., Trujillo, A., Fagni, T.: Personalized interventions for online moderation. In: Proceedings of the 33rd ACM Conference on Hypertext and Social Media, pp. 248–251 (2022)
  * [5] Horta Ribeiro, M., Jhaver, S., Zannettou, S., Blackburn, J., Stringhini, G., De Cristofaro, E., West, R.: Do platform migrations compromise content moderation? Evidence from r/The_Donald and r/Incels. Proceedings of the ACM on Human-Computer Interaction 5(CSCW2), 1–24 (2021)
  * [6] Trujillo, A., Cresci, S.: Make Reddit Great Again: Assessing community effects of moderation interventions on r/The_Donald. Proceedings of the ACM on Human-Computer Interaction 6(CSCW2), 1–28 (2022)
  * [7] Trujillo, A., Cresci, S.: One of Many: Assessing User-level Effects of Moderation Interventions on r/The_Donald. In: Proceedings of the 15th ACM Web Science Conference 2023, pp. 55–64 (2023)
  * [8] Pierri, F., Pavanetto, S., Brambilla, M., Ceri, S.: Vaccinitaly: monitoring italian conversations around vaccines on twitter (2021)
  * [9] Blondel, V.D., Guillaume, J.-L., Lambiotte, R., Lefebvre, E.: Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment 2008(10), 10008 (2008). doi:10.1088/1742-5468/2008/10/P10008
  * [10] Kleinberg, J.M., et al.: Authoritative sources in a hyperlinked environment. In: SODA, vol. 98, pp. 668–677 (1998)
  * [11] Hanu, L., Unitary team: Detoxify. Github. https://github.com/unitaryai/detoxify (2020)
  * [12] Rossetti, M., Zaman, T.: Bots, disinformation, and the first impeachment of us president donald trump. Plos one 18(5), 0283971 (2023)
  * [13] Maleki, M., Arani, M., Buchholz, E., Mead, E., Agarwal, N.: Applying an epidemiological model to evaluate the propagation of misinformation and legitimate covid-19-related information on twitter. In: Social, Cultural, and Behavioral Modeling: 14th International Conference, SBP-BRiMS 2021, Virtual Event, July 6–9, 2021, Proceedings, pp. 23–34 (2021). Springer