{'fraction_non_alphanumeric': 0.04153102259670624, 'fraction_numerical': 0.016253351206434317, 'mean_word_length': 4.079270516717325, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 16, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
PAC-Bayesian Lifelong Learning For Multi-Armed Bandits

We present a PAC-Bayesian analysis of lifelong learning. In the lifelong learning problem, a sequence of learning tasks is observed one-at-a-time, and the goal is to transfer information acquired from previous tasks to new learning tasks. We consider the case when each learning task is a multi-armed bandit problem. We derive lower bounds on the expected average reward that would be obtained if a given multi-armed bandit algorithm was run in a new task with a particular prior and for a set number of steps. We propose lifelong learning algorithms that use our new bounds as learning objectives. Our proposed algorithms are evaluated in several lifelong multi-armed bandit problems and are found to perform better than a baseline method that does not use generalisation bounds.


Introduction
Lifelong machine learning [44] is a framework in which a system continually observes new learning tasks and attempts to use its experience with previous tasks to perform new tasks more efficiently. Baxter [6] proposed a formal model of lifelong learning in which the problem can be studied. In this model, each task is a supervised learning problem that comprises an unknown input-label distribution and several inputlabel pairs sampled independently from this distribution. The goal of each task is to select a hypothesis that accurately predicts the labels of newly sampled inputs. The goal of the lifelong learning system is to learn an inductive bias using data from several tasks that will allow a learning algorithm to select a hypothesis that makes accurate predictions on a new task. The degree to which tasks are related is specified by a task environment. This is a fixed unknown distribution over a set of possible input-label distributions that determines which tasks are likely to appear next. It is often assumed that every new task is sampled independently from the task environment.
For example, the goal of each task could be to predict whether various flu treatments are effective against a particular flu strain. The task environment could be a distribution over flu strains. Having seen examples from several strains, a lifelong learning system may discover that, against all of these strains, treatment A is effective. The learned inductive bias may then favour hypotheses where treatment A is predicted to be effective.
In this work, we present a PAC-Bayesian [42] [31] analysis of the lifelong learning problem. [32], [1] and [35] have proposed PAC-Bayesian generalisation bounds that apply to Baxter's model. They quantify the difference between the average error on a set of observed data sets and the expected error on a new task sampled from the task environment. Lifelong learning algorithms can use these PAC-Bayesian bounds to identify prior distributions over hypotheses that are expected to generalise well to new tasks. These existing PAC-Bayesian lifelong learning bounds only apply to lifelong supervised learning. However, it has been shown that learning from multiple tasks can also be beneficial for multi-armed bandits [2] [43] and reinforcement learning [27] [8] [13]. This motivates the development of PAC-Bayesian bounds for lifelong learning that apply to sequential decision problems.
We provide PAC-Bayesian generalisation bounds for lifelong learning in an extension of Baxter's model [6], where each task is a multi-armed bandit (MAB) problem. In a MAB problem, there are K actions (or arms), each associated with an unknown reward distribution. There is a fixed number of rounds m and in each round, an action/arm is selected and a reward is sampled from the corresponding reward distribution. The goal is to select actions that maximise the cumulative sum of rewards. Returning to the flu treatment example, the goal of each task could be to choose the best flu treatments for a small sequence of patients. The task environment could be a distribution over flu strains, each one with its own set of reward distributions. A lifelong learning system may learn to start each new task by trying out a treatment that worked well against many of the previous flu strains.
Switching from supervised learning tasks to MAB tasks introduces several challenges. First of all, we no longer have data sets for each task that are i.i.d.. The data set for each task includes actions selected by the lifelong learning system. In general, these actions are dependent on previous training data from the current task and from previous tasks. Next, there is the problem of limited feedback. In supervised learning problems, any predicted label can be evaluated on every input-label pair in the training data set. In multi-armed bandit tasks, predicted actions can only be evaluated using observed action-reward pairs that contain the predicted action. Data dependence and limited feedback make quantifying our uncertainty about the unknown task environment and the unknown reward distributions for each task more difficult.
The contributions of this work are as follows: 1. We derive the first PAC-Bayesian generalisation bounds for lifelong learning of multi-armed bandit tasks.

PAC-Bayesian Bounds
This section provides a brief introduction to PAC-Bayesian analysis [42] [31]. As an example, we present the PAC-Bayesian Bernstein inequality by [39], applied to the MAB problem. Consider a MAB problem with a discrete set of actions A and a reward distribution ρ(r|a) that is conditioned on the action chosen. Assume that rewards are always between 0 and 1. Let D = {(a i , r i )} m i=1 be a training data set containing m action-reward pairs and let D :j denote the first j action-reward pairs in D. Each action a i is sampled from a behaviour policy b i , which can depend on all previous observations. Let r i be a sample from the reward distribution ρ(r|a i ). Let the expected reward for an action a be defined as: Given a training data set D, the expected reward can be approximated by an unbiased estimator called the importance-weighted empirical reward. For an action a and dataset D, this is defined as: For a distribution Q over actions, let R(Q) = E a∼Q [R(a)] and R(Q, D) = E a∼Q [ R(a, D)]. The aim is to find a Q that maximises the expected reward R(Q). However, if ρ(r|a) is unknown, only R(Q, D) can be computed. The PAC-Bayesian Bernstein bound by [39] can be used to upper bound the difference between R(Q, D) and R(Q). From the upper bound on this difference, one can obtain a lower bound on R(Q) that consists of only observable quantities. Theorem 1 states the resulting lower bound, and is a restatement of Theorem 1 of [39].
Theorem 1 ( [39]). Let {b 1 , b 2 , . . . } be any sequence of sampling distributions that are bounded below by { 1 , 2 , . . . } (meaning b m (a) ≥ m for all a ∈ A and m ≥ 1). Let {P 1 , P 2 , . . . } be any sequence of reference distributions over A, such that P m is independent of D :m (but can depend on m). Let {λ 1 , λ 2 , . . . } be any sequence of positive numbers that satisfy: Then for all possible distributions Q m over A given m and for all m ≥ 1 simultaneously with probability greater than 1 − δ This bound states that, with probability at least 1 − δ and for all rounds m ≥ 1, the expected reward is lower bounded by the empirical reward for Q m plus a complexity term containing the KL divergence between Q m and the reference distribution P m , which must be chosen before observing the training data. This lower bound can be used as an objective function for finding a Q m that maximises R(Q m ). It also motivates learning useful priors, for example from previous tasks. If P m is chosen such that there is a Q m with high empirical reward and where D KL (Q m ||P m ) is small, then the lower bound on R(Q m ) will be large.

Problem Setup
We represent a multi-armed bandit (MAB) task as a couple where A is a finite set of actions and ρ i (r|a) is a distribution over rewards r that is conditioned on the action a ∈ A. We assume that rewards are always between 0 and 1 and that tasks are sampled i.i.d. from an environment T .
In each task, the lifelong learning algorithm chooses a sequence of behavior policies {b ij } m j=1 that is used to sample the actions of a data set D i = {(a ij , r ij )} m j=1 . b ij is a distribution over actions that can depend on all previously observed training data D 1 , . . . , k=1 is the first j − 1 action reward pairs for task i. We assume that the training data set for every task contains m action-reward pairs. Therefore, the elements of each training data set are distributed as follows: In the interest of concise notation, we will let b ij (a) denote the probability mass functions of the behaviour policies conditioned on all previous training data. Let M(A) denote the set of all probability distributions over A and let D denote the set of all possible training data sets. To solve each task, a deterministic learning algorithm A : D × M(A) → M(A) takes a data set D i and a prior P as inputs and produces a posterior Q = A(D i , P ). We refer to P as a prior and Q as a posterior since P must be chosen before observing any training data from the current task, whereas Q can be chosen afterwards. For task i, the expected reward for an action a is: Using the training set D i , the expected reward can be estimated with an importance-weighted empirical reward estimate: Due to the potentially very large importance sampling weights 1/b ij (a ij ), this reward estimate can have very high variance depending on the choice of b ij . This can be addressed by constraining b ij or by clipping the importance sampling weights to the range [0, 1 + τ ]. Define the clipped importance-weighted reward estimate as: The importance-weighted estimate is an unbiased estimate of the expected reward, and since clipping the importance sampling weights cannot increase the value of reward estimate, we have that: and The inductive bias that the lifelong learning system must learn is the prior P . To derive PAC-Bayesian bounds for lifelong learning, we require the notions of a hyperprior and a hyperposterior. The hyperprior P and hyperposterior Q are both distributions over the set of possible priors. The hyperprior must be chosen before we observe data from any tasks, whereas the hyperposterior can be chosen afterwards. A well-chosen hyperposterior will assign high probability mass/density to priors that result in posteriors with high expected reward on new tasks. We measure the performance of a hyperposterior by the marginal transfer reward, which is the expected value of the average reward obtained in the first m rounds on a new task T n+1 when using the base learning algorithm A with a prior P sampled from Q.
It is called marginal because the expectation with respect to (T n+1 , D n+1 ) is not conditioned on the observed tasks and training data sets (T 1 , D 1 ), . . . , (T n , D n ). Since the task environment is unknown, the marginal transfer reward cannot be calculated and so we cannot directly maximise it with respect to the hyperposterior. Therefore, we will instead maximise lower bounds on the marginal transfer reward. The PAC-Bayesian bounds in this work bound the difference between the marginal transfer reward and the following empirical estimates, called the (clipped) empirical multi-task reward We split the task of bounding the difference between the marginal transfer reward and the empirical multi-task reward into two steps. First, we bound the difference between the marginal transfer reward and an intermediate quantity called the expected multi-task reward. The expected multi-task reward is defined as: We then bound the difference between the expected and empirical multi-task reward. Finally, we add this difference to the first difference to obtain a lower bound on the marginal transfer reward.

Simplifying Assumptions
Recall from section 3.1, that we assume the tasks T 1 , T 2 , . . . are sampled i.i.d. from the task environment. This means that the reward distributions ρ i are independent of each other, but the task data sets D i , which are the only observable quantities, are still dependent on each other since each behaviour policy may depend on data from previous tasks.
We make two simplifying assumptions that make bounding the marginal transfer reward more feasible. Only the first assumption is necessary to derive our bounds and to select the hyperposterior that maximises the bounds. If we want to evaluate the bounds, the second assumption allows us to deal with a term in our bounds that cannot easily be computed.
Our first assumption restricts how the expected reward for each task can be related to the expected reward of previous tasks. We assume that the marginal expected reward for any prior P and any number of training samples j is greater for task n + k than it is for task n. More precisely, it is assumed that for all 1 ≤ j ≤ m and n, k ∈ N Since we have assumed that the tasks T 1 , T 2 , . . . are i.i.d., the expected reward for tasks n and n + k can only be different if D n and D n+k have different distributions, which happens when the behaviour policies for each task are different. Therefore, this assumption requires that the posterior resulting from data sampled with the behaviour policies for task n + k does not have lower expected reward than the posterior resulting from running the behaviour policies for task n. Our proposed algorithms always use behaviour policies that depend greatly on the current hyperposterior. Since the hyperposterior is continually being improved after each new task is observed, we expect this assumption to hold.
Our second assumption restricts how strongly the expected reward for each task can depend on data from previous tasks. We assume that with high probability (over the set of observed tasks and datasets ( In other words, once a sufficiently large number of tasks and data sets have been observed, the specific set of observed data sets has a negligible effect on the expected value of the average of the first m rewards, for a high proportion of possible sets of observed tasks and data sets. This assumption holds whenever the sequence of expected rewards converges to the same value. Since we have assumed that the tasks are sampled from a fixed distribution, we expect that this is the case for our setting.

Main Results
The derivation of our main results can be split into two parts. Firstly, in Lemma 3, we obtain a bound on the difference between the marginal transfer reward and the expected multi-task reward. This bound quantifies our uncertainty about the environment T , given a sample of tasks T 1 , . . . , T n . Secondly, in Lemma 6 and Lemma 8, we obtain bounds on the difference between the expected multi-task reward and the empirical multi-task reward. Our main results are obtained by combining these lemmas.
We will begin by stating some auxiliary lemmas that will be used in the proof of Lemma 3. The first is a change of measure inequality from [14] and is referred to as the compression lemma in [5]. We will also refer to it as the compression lemma.
Lemma 1 (Compression Lemma [14,5]). For any measurable function f (x) on X and any distributions q and p on X , the following inequality holds The second auxiliary lemma is Hoeffding's lemma [23].
Now we are ready to state our bound on the difference between the marginal transfer reward and the expected multi-task reward.
Lemma 3. If condition (1) is satisfied, then for any hyperprior P, any λ > 0 and any δ ∈ (0, 1], inequality (3) holds with probability at least 1 − δ over the tasks and training sets (T 1 , D 1 ), . . . , (T n , D n ) and for all hyperposteriors Q where ). If the assumption in Equation (1) holds, then the marginal transfer reward R(Q) can be lower bounded as follows: Now, we need to upper bound the following quantity: We first rewrite this difference as: From the definition of c n in the statement of the lemma, we have that the second line of Equation (4) is upper bounded by c n . Next, we upper bound the first line of Equation (4). Using the compression lemma, for any λ > 0, we have that: where P is another distribution over priors. Next, the exponential term in Equation (5) must be upper bounded. It can be rewritten as a product of exponentials. Then, for any δ ∈ (0, 1], using Markov's inequality with respect to expectations over (T 1 , D 1 ), . . . , (T n , D n ), the following inequality holds with probability at If P does not depend on the observed tasks and training sets (T 1 , D 1 ), . . . , (T n , D n ), e.g. P is chosen before observing any tasks, then the order of expectations can be swapped. Since each task T i is sampled i.i.d. from T and each training set D i depends only on the training sets that came before it, the expectation over (T 1 , D 1 ), . . . , (T n , D n ) can be factorised as follows Hoeffding's lemma can be used, with to upper bound the nth term in the product.
Through alternating steps of factorisation and application of Hoeffding's lemma, we have that Substituting this into Equation (5), we have that for any δ ∈ (0, 1] and any λ > 0, with probability at Combining this with Equation (4) and the fact that c n upper bounds the second line of Equation (4), we have that, with probability at least 1 − δ: Next, we state our first bound on the difference between the expected multi-task reward and the empirical multi-task reward, which is based on the PAC-Bayesian Bernstein inequality for martingales [39]. First, we state some auxiliary lemmas.
. . , X i−1 be the cumulative variance of this martingale. Then for any λ ∈ [0, 1/c]: To utilise Lemma 4, we construct a martingale difference sequence from the training data of each task. Define: If we let b min = min i≤n,j≤m,a∈A (b ij (a)) and assume b min > 0, then X ij (a) ≤ 1/b min for all i, j and a. Next, we verify that X ij (a) form a martingale difference sequence. For any i ≤ n and j ≤ m: be the cumulative variance of this martingale. We use the following upper bound on V ij (a) from [39]: ). For any i ≤ n, any j ≤ m and any a ∈ A: Finally, let (Q, A n k ) denote the joint distribution over (P, a 1 , . . . , a n ) where P ∼ Q and a i ∼ A(D :k i , P ) for i = 1, . . . , n. Similarly, let (P, P n ) denote the joint distribution over (P, a 1 , . . . , a n ) where P ∼ P and a i ∼ P for i = 1, . . . , n. We have that Now we are ready to state and prove our bound on the difference between R(Q) and R(Q).
Lemma 6. For any hyperprior P, any λ ∈ [0, mb min ], and any δ ∈ (0, 1], inequality (7) holds with probability at least 1 − δ over the training sets {D 1 , . . . , D n } and for all hyperposteriors Q Proof. Using the compression lemma, we have that for any k = 1, . . . , m Now, we need to upper bound the term inside the logarithm. For any δ ∈ (0, 1], using Markov's inequality with respect to expectations over D 1 , . . . , D n , the following inequality holds with probability greater than If P does not depend on any of the training sets D 1 , . . . , D n , then the order of the expectations can be swapped. Since each training set is only dependent on the training sets that came before it, the expectation over D 1 , . . . , D n can be factorised.
Using Lemma 4, the nth term of the product can be upper bounded.
By rearranging this inequality and applying the cumulative variance bound from Lemma 5, we have that with probability at least 1 − δ: Using the union bound, if we replace ln(1/δ) with ln(m/δ), then Equation (9) holds simultaneously for all k = 1, . . . , m with probability at least 1 − δ. From the definitions of R(Q), R(Q) and M ij (a): Substituting in the result of Equation (9), we have that with probability at least 1 − δ: By using Equation (6) and rearranging this inequality, we obtain: Finally, the substitution λ = mλ yields the statement of the lemma. The requirement λ ∈ [0, b min ] then becomes λ ∈ [0, mb min ].
Next we state our bound on the difference between R τ (Q) and R(Q). Instead of Bernstein's inequality, this bound uses the Hoeffding-Azuma inequality for supermartingales with bounded differences [3] [12]. A proof can be found in the appendix.
Then for any λ > 0: To utilise Lemma 7, we construct supermartingales with bounded differences from the training data of each task. Define: Due to the clipped importance sampling weight, X τ ij (a) ∈ [0, 1 + τ ] for all i ≤ n, j ≤ m and a ∈ A. Next, we verify that {X τ ij (a)} m j=1 is a supermartingale difference sequence. For any i ≤ n and j ≤ m: Now we state our bound on the difference between R(Q) and R τ (Q) in Lemma 8. The proof of Lemma 8 follows the proof of Lemma 6 except that each application of Bernstein's inequality is replaced with an application of Lemma 7. Therefore, we state the proof in the Appendix.
Lemma 8. For any hyperprior P, any λ > 0, any τ > 0 and any δ ∈ (0, 1], inequality (11) holds with probability at least 1 − δ over the training sets {D 1 , . . . , D n } and for all hyperposteriors Q Now we are ready to state two lower bounds on the marginal transfer reward, which are our main results. First, we can combine the results from Lemma 3 and from Lemma 6 to obtain our first lower bound.
The proof of Theorem 3 can be found in the appendix. The technique of bounding the difference between R(Q) and R τ (Q) by adding bounds on the difference between R(Q) and R(Q) and the difference between R(Q) and R τ (Q) is borrowed from [32]. However, the two bounds being added together are both novel.
The lower bounds in Theorem 2 and Theorem 3 contain two complexity penalties. The first is the KL divergence between the hyperposterior and the hyperprior. This penalty is small when the hyperposterior is close to the hyperprior. The second is the expected average KL divergence between the posteriors returned by the base learning algorithm and the priors. This penalty is small when the hyperposterior assigns high probability density to priors that are close to the posteriors returned by the base learning algorithm.
The asymptotic behaviour of the bounds depends on the values of λ 1 and λ 2 . If the assumption in Equation (2) is satisfied, then c n decays to 0 as n → ∞ with high probability. If we ignore this term, then the difference between the marginal transfer reward and the (clipped) empirical multi-task reward is of order

Algorithms For Lifelong Multi-Armed Bandits
We propose lifelong learning algorithms that use the lower bounds in Theorem 2 and Theorem 3 as their objective functions. These algorithms use either variational inference (VI) or Markov chain Monte Carlo (MCMC) to approximate the hyperposterior that maximises the lower bound. First, we will describe the characteristics that the algorithms all share.
Each prior P and posterior Q is a probability vector with K = |A| elements. The ath element is the probability of selecting action a. We restrict priors to be the softmax of a weight vector w ∈ R K . This means that the hyperprior and hyperposterior can be any distribution over R K . Let P w denote the prior probability vector that is softmax of w. The choice of base learning algorithm is somewhat arbitrary. The only requirements are that it should take a prior P over actions and a dataset D as inputs and return a posterior Q over actions. Since we will need to compute the posterior returned by the base learning algorithm many times when evaluating the lower bound, it is preferable for the posterior returned by the base learning algorithm to have a closed-form solution. With these points in mind, we use the following base learning algorithm: I a is the set of indices where a ij = a. The posterior returned by this base learning algorithm has the following closed-form solution: Each behaviour policy can be set equal to the current posterior Q. Since the Bernstein bound in Theorem 2 depends on b min = min i≤n,j≤m,a∈A (b ij (a)), we instead set the behaviour policy to be an -soft version of the current posterior when using this bound. That is, with probability 1 − , actions are sampled from Q, and with probability , actions are sampled uniformly at random. This guarantees that b min ≥ /K, where K is the number of actions. Therefore, b min in Theorem 2 can be replaced with /K.
We set λ 1 = T 1 √ n and λ 2 = T 2 √ m, where T 1 and T 2 are positive temperature parameters. Since λ 1 and λ 2 must be chosen in advance and cannot depend on any observed data for our bounds to be valid, T 1 and T 2 must also be chosen in advance. Optionally, one can use the bound value to inform the choice of the temperature parameters. First, a grid of (say N ) T 1 and T 2 values can be constructed. Then, using a union bound argument, if we replace δ with δ/N , then either of our lower bounds holds simultaneously for each T 1 and T 2 with probability greater than 1 − δ. Then one can use the lower bound with whichever pair of T 1 and T 2 maximises its value as an objective function. This approach could result in nearly the best possible bound value, but will not necessarily result in the best reward obtained. In our experiments, we run our algorithms several times with different fixed values of T 1 and T 2 , and we find that the values of T 1 and T 2 that give the best bound values do not give the best performance in terms of reward.
Both our proposed lifelong learning algorithms approximate the hyperposterior that maximises one of our lower bounds. If we are using the Bernstein bound in Theorem 2, this hyperposterior is the solution of the following optimisation problem:

Variational Inference
Here, we describe an algorithm that approximates the solution of the optimisation problem in Equation (14) with variational inference techniques. We describe the algorithm using the Bernstein bound as an example, but the method works in the same way with the clipping bound from Theorem 3. We instead solve a slightly different optimisation problem: Q θ is a member of a parametric family of distributions with parameter θ. We choose Q θ = N (µ Q , σ Q I), so θ = (µ Q , σ Q ), and P = N (µ P , σ P I). Our goal is now to find the optimal θ.

Algorithm 1 PAC-Bayes VI
Input: Task distribution T , base learning algorithm A, hyperprior P, temperature parameters T 1 , T 2 Initialise hyperposterior Q θ ← P for i = 1 to n do Sample task T i ∼ T Sample prior P w ∼ Q θ Initialise task posterior Q ← P w Initialise task dataset D i ← () for j = 1 to m do Get behaviour policy b ij ← B(Q, ) Sample a ij ∼ b ij (a) and r ij ∼ ρ i (r|a ij ) Append (a ij , r ij ) to D i Update task posterior Q ← A(D i , P w ) end for for k iterations do θ ← θ + η ∂ ∂θ L VI (θ) (or Adam) end for end for We use Monte Carlo approximations of the expected values in Equation (15). In particular, where each w ij is an independent sample from Q θ . With these Monte Carlo approximations, the objective function used in the algorithm is: We use Adam [24] to maximise the lower bound with respect to θ. Gradients of the Monte Carlo approximations with respect to θ are computed using the reparameterisation trick [25]. We call this algorithm PAC-Bayes VI. Algorithm 1 provides pseudocode for PAC-Bayes VI. In Algorithm 1, B(Q, ) denotes the -soft version of Q. Note that if the clipping bound is used, then there is no need to use an -soft version of Q as a behaviour policy.
Since D KL (Q θ ||P) is available in closed-form, the value of the lower bound at Q θ can be easily computed if we assume that c n = 0.

Markov Chain Monte Carlo
Here, we describe an algorithm that uses Markov Chain Monte Carlo (MCMC) techniques to draw samples from the hyperposterior that is solution to the optimisation problem in Equation (14). Firstly, define We have that The optimisation problem in Equation (14) can be rewritten as This type of problem appears frequently in the PAC-Bayesian literature and has previously been studied by [11], [22]. It is known that the Gibbs distribution is the solution. In this case, the Gibbs distribution has the probability density function Q(w) ∝ P(w)e φ(w) .
Furthermore, the maximum value attained by the Gibbs distribution is: Though we can only compute the unnormalised density function of the Gibbs distribution, we can still sample it using MCMC. We choose P = N (µ P , σ P I) and we use Preconditioned Stochastic Gradient Langevin Dynamics (pSGLD) [28] to draw samples from P(w)e φ(w) . We call this algorithm PAC-Bayes MCMC. Algorithm 2 provides pseudocode for PAC-Bayes MCMC.
This time, D KL (Q||P) is not available in closed-form. However, we can use equation (16) to rewrite the Bernstein (or clipping) lower bound as:

Algorithm 2 PAC-Bayes MCMC
Input: Task distribution T , base learning algorithm A, hyperprior P, temperature parameters T 1 , T 2 Initialise prior weight vector w ∼ P for i = 1 to n do Sample task T i ∼ T Set prior P ← P w Initialise task posterior Q ← P Initialise task dataset D i ← () for j = 1 to m do Get behaviour policy b ij ← B(Q, ) Sample a ij ∼ b ij (a) and r ij ∼ ρ i (r|a ij ) Append (a ij , r ij ) to D i Update task posterior Q ← A(D i , P ) end for for k iterations do w ← pSGLD step(w, P(w)e φ(w) ) end for end for All that remains is to calculate or approximate ln Ew∼P e φ(w) . We can apply Jensen's inequality to obtain a lower bound that can easily be approximated with a standard Monte Carlo estimate: As shown in [9], if we replace e φ(w) with an average of several samples 1 K K k=1 e φ(w k ) from P, then the lower bound on ln E w∼P e φ(w) approaches the true value as K goes to infinity:

Experiments
We tested our proposed lifelong learning algorithms in three environments. In each environment, tasks are multi-armed bandit problems with 10 or 20 actions and binary rewards. The reward distribution for action a is a Bernoulli distribution with parameter p a . The distribution over each p a is a Beta distribution with parameters α a and β a . Therefore, sampling a new task from the environment means sampling the parameter p a for each arm from a Beta distribution with parameters α a and β a . In environment one, the shape parameters of the Beta distributions are as follows: When sampling tasks from this environment, the expected values of p 0 , . . . , p 7 are all 0.2 and the expected values of p 8 and p 9 are both 0.8. p a has small variance for every a. Each task sampled from this environment will be very similar, and in almost every task sampled from this environment, there will be 2 good actions and 8 bad actions. A good prior for tasks sampled from this environment would assign high probability to actions 8 and 9, reducing the problem of choosing between 10 actions to choosing between the two good actions. The second environment is the same as the first environment, except with 20 actions instead of 10 actions. The proportions of good and bad actions is still the same. In environment two, the shape parameters of the Beta distributions are: 17, 18, 19} .
The third environment also has 20 actions. The shape parameters of the Beta distributions are: (5,20) if i = 10 (  In environment three, p a has large variance for the first 10 actions and small variance for the last 10 actions. The expected value of p a is 0.2 for the first 10 actions and increases linearly from 0.2 to 0.8 for actions 10 to 19. In environment three, it is more difficult to identify which actions tend to have the best rewards and therefore harder to learn a useful prior. Figure 1 shows the probability density of p a for each action in environments two and three. The densities for environment one are the same as those of environment two, except with only 10 total actions. We compared our PAC-Bayes VI and PAC-Bayes MCMC algorithms with both bounds against two benchmark methods. The first benchmark uses the base learning algorithm with a uniform prior for every task. We call this benchmark Learning From Scratch (LFS). The second benchmark is called Adaptive Ridge Regression (ARR) [32]. It uses the base learning algorithm for every task, initially with a uniform prior. After every task, the prior is set to be equal to the average of the posterior distributions learned on all previous tasks. If p n+1 (a) is the ath element of the prior probability vector for task n + 1 and q i (a) is the ath element of the posterior probability vector from task i, then In each experiment, m = 20 action-reward pairs were sampled from each task and the number of tasks ranged from n = 1 to 100. We tested our algorithms with temperature constants (T 1 , T 2 ) ∈ {(5, 1), (15,3), (50, 10)} and reported results with each. For the Bernstein bound, we additionally tested T 1 = 5 and T 2 = ( /K) √ m, which is the largest possible value for T 2 such that the bound is valid. We recorded the average of the m rewards obtained in each task as well as the value of the each lower bound. The reported bound values assume that c n = 0. Returning to our second assumption in Sect. 3.2, this means we have assumed that n is large enough for c n to have decayed to 0. Each run of the experiment was an average of 10 runs. We repeated this 50 times and we report the mean and standard deviation of the average reward.  First, we investigate the performance of our algorithms when the hyperprior is uninformative. Recall from the beginning of Sect. 4, that the hyperprior is a distribution over the weight vector of a softmax policy. For our experiments with an uninformative hyperprior, we use a standard Gaussian distribution as the hyperprior. Figure 2 shows the average reward obtained with the baselines and with PAC-Bayes VI and PAC-Bayes MCMC in environment one. The values of the Bernstein and clipping bounds are also shown.  In Figure 2, ARR reached an average reward of 0.779 by task 100. When the Bernstein bound was used and was 0.05, PAC-Bayes VI and PAC-Bayes MCMC with T 1 = 50 and T 2 = 10 reached only 0.753 and 0.749, respectively. When was 0.1 or 0.2, the average reward for both PAC-Bayes algorithms plateaued at a lower average reward. When the clipping bound was used, PAC-Bayes VI with the highest temperatures and τ equal to 0.1, 0.2 and 0.5 reached average rewards of 0.788, 0.791 and 0.798 respectively, which is slightly higher than that of ARR. At the highest temperatures, PAC-Bayes MCMC was slightly worse, reaching only 0.762, 0.763 and 0.736 respectively for each value of τ .  In Figure 2, the Bernstein bound on the marginal transfer reward was below 0 for every value of . Unsurprisingly, given the explicit dependence of the bound on , increasing resulted in greater lower bound values. The clip bound was greater than 0 for PAC-Bayes VI with T 1 = 15 and T 2 = 3. For τ equal to 0.1, 0.2 and 0.5, the bound values at this temperature and after 100 tasks were 0.227, 0.238 and 0.202 respectively. Particularly at the highest temperatures, the clip bound value for the MCMC version was far below the clip bound value for the VI version. Figure 3 shows the average reward and bound values obtained in environment two.  Recall that in environment one (Figure 2), ARR reached higher average reward than our PAC-Bayes algorithms when the Bernstein bound was used. In environment two, this was no longer the case. In Figure  2 ARR reached an average reward of 0.720. At the highest temperatures, and when was 0.05, PAC-Bayes VI and PAC-Bayes MCMC reached average rewards of 0.764 and 0.771 respectively. When the clip bound was used, PAC-Bayes VI with the highest temperatures and τ equal to 0.1, 0.2 and 0.5 reached average rewards of 0.794, 0.796 and 0.784 respectively, which is almost the same as in environment one. At the highest temperature, PAC-Bayes MCMC was once again slightly worse, reaching only 0.778, 0.776 and 0.758 respectively for each value of τ .
In Figure 3, the Bernstein bound was below 0 for every value of . Unlike in environment one, the clip bound was below 0 for every temperature and every value of τ . The lower bound values at the medium and lower temperatures were likely worse here than in environment one because the average rewards at these temperatures were lower in environment two. The highest bound value was -0.071, reached by PAC-Bayes VI after 100 tasks with T 1 = 15, T 2 = 3 and τ = 0.5. Figure 4 shows the average reward and bound values obtained in environment three.
In Figure 4, ARR reached an average reward of 0.626 by task 100. When the Bernstein bound was used and was 0.05, PAC-Bayes VI and PAC-Bayes MCMC with the highest temperatures reached 0.689 and 0.691 respectively. As in the previous two environments, when the clip bound was used, PAC-Bayes VI reached higher average reward than PAC-Bayes MCMC at the highest temperatures. With the highest temperatures and τ equal to 0.1, 0.2 and 0.5, PAC-Bayes VI reached average rewards of 0.715, 0.703 and 0.710 respectively. PAC-Bayes MCMC reached average rewards of 0.666, 0.645 and 0.629 respectively. In the bottom two rows of Figure 4, the Bernstein lower bound was once again below 0 for every value of . The clip lower bound was below 0 for every temperature and every value of τ .
Lastly, we tested our algorithms once more in environment three, but this time with a more informative hyperprior. The hyperprior is still a diagonal Gaussian distribution over the weight vector of a softmax policy, but this time the last element of the mean vector is 2 instead of 0. Therefore, priors sampled from this informative hyperprior are likely to assign a higher probability to the last action than the other actions. Since the last action is usually the best action, for tasks sampled from environment three, we expect this hyperprior to improve the average reward and bound values obtained. Our results with this informative hyperprior are shown in Figure 5.
In Figure 5, when the Bernstein bound was used and was 0.05, PAC-Bayes VI and PAC-Bayes MCMC with the highest temperatures reached an average rewards of 0.681 and 0.678 respectively. These average rewards with the informative hyperprior are almost no different from the corresponding average rewards in Figure 4, where the uninformative hyperprior was used. However, when the clip bound was used, both PAC-Bayes VI and PAC-Bayes MCMC reached higher average rewards with the informative hyperprior. With the highest temperatures and τ equal to 0.1, 0.2 and 0.5, PAC-Bayes VI reached average rewards of 0.797, 0.792 and 0.787 respectively. PAC-Bayes MCMC reached average rewards of 0.785, 0.778 and 0.777 respectively.
In the bottom two rows of Figure 5, even when using the informative hyperprior, the Bernstein bound was below 0 for every value of . However, the clip bound was above 0 when PAC-Bayes VI was run with the medium (T 1 = 15, T 2 = 3) or low (T 1 = 5, T 2 = 1) temperatures. At the medium temperatures, the bound values after 100 tasks when τ was 0.1, 0.2 and 0.5 were 0.339, 0.331 and 0.277.
Our results suggest that, when run with high enough values of the temperature parameters, our PAC-Bayes algorithms can obtain higher average reward than ARR. PAC-Bayes VI with the clip bound consistently reached the highest average reward when run with the highest temperatures and any value of τ . PAC-Bayes VI with the clip bound also produced the best bound values. In environment one and environment three with the informative hyperprior, it was possible to obtain close to the best average reward and a non-trivial lower bound value simultaneously by running PAC-Bayes VI with the clip bound and with T 1 = 15, T 2 = 3. In general, higher temperatures yielded higher average reward whereas the best bound values were achieved with medium or low temperatures. This suggests that using the bound value to select the temperature parameters, as discussed in Sect. 4, may result in sub-optimal average reward.

Related Work
Lifelong learning is related to problems in which the goal is to learn from a set of tasks. In multi-task learning [10], the goal is to learn multiple tasks simultaneously. In domain adaptation [7], the goal is to learn one task, using data from other tasks. In meta learning [37], the goal is to learn a learning algorithm from a set of tasks that performs well on new tasks. Approaches that use PAC-Bayesian analysis for these problems are closely related to this work. For example, PAC-Bayesian methods for domain adaptation [19] [20] [21] and meta learning [1] [35].
The first PAC-Bayesian lifelong learning bound [32] has since been extended to certain situations where tasks are not sampled i.i.d. from a task environment [33]. This extension considers the case where the task data distributions are sampled from the same distribution, but not independently, and also the case where tasks are sampled independently, but the task environment changes over time.
PAC-Bayesian bounds have previously been derived for single multi-armed bandit problems [41] [39] and contextual bandit problems [38]. These results made heavy use of PAC-Bayesian martingale concentration inequalities [40]. Subsequent PAC-Bayesian inequalities for martingales [46] [4] may therefore also prove useful for studying the multi-armed bandit and contextual bandit problems.
Several works have applied PAC-Bayesian analysis to offline bandit problems. In offline bandit problems, the training data are all sampled from a single, fixed behaviour policy. This means that action-reward pairs are independent of each other. PAC-Bayesian bounds for the clipped importance-weighted reward estimate [29] and for a self-normalised weighted importance sampling estimate [26] have been derived in the offline setting.
PAC-Bayesian bounds for model selection [16] and policy evaluation [17] have been derived in the reinforcement learning setting. Finally, PAC-Bayesian bounds have been derived for out-of-distribution generalisation [30], [45] [34] and out-of-distribution detection [18] in reinforcement learning problems.