PaperlayerView exact revision on arXiv

Source-linked AI summary

Sequential Transfer in Multi-armed Bandit with Finite Set of Models

Mohammad Gheshlaghi Azar, Alessandro Lazaric, Emma Brunskill

arXiv:1307.6887v1stat.MLcs.LG

TL;DR

Transfer in online learning is less studied than batch transfer, though it matters for learning across tasks. The paper estimates latent bandit models from sequential task data and transfers those estimates with tUCB. The algorithm is guaranteed not to perform worse than UCB per episode, and approaches mUCB's performance as tasks accumulate.

  • Problem

    Transfer research has mostly focused on batch tasks, while sequential online transfer in multi-armed bandits remains less studied.

    Source: §1 · p. 1

  • Method

    The paper uses the robust tensor power method to estimate latent bandit-model means and transfers those estimates through tUCB.

    Source: §1 · p. 1, §4 · p. 3, §4.1 · p. 4

  • Results

    tUCB is guaranteed to perform as well as UCB in early episodes and then approach the ideal known-model-set performance.

    Source: §1 · p. 2

  • Takeaways & Limitations

    As more tasks are observed, tUCB transfers increasingly accurate model knowledge and approaches mUCB's performance.

    Source: §6 · p. 8

    tUCB's per-episode regret guarantee does not establish optimal cumulative regret; with many episodes, earlier model identification may improve later performance at higher early regret.

    Source: §6 · p. 8

Abstract

from arXiv · show

Learning from prior tasks and transferring that experience to improve future performance is critical for building lifelong learning agents. Although results in supervised and reinforcement learning show that transfer may significantly improve the learning performance, most of the literature on transfer is focused on batch learning tasks. In this paper we study the problem of \textit{sequential transfer in online learning}, notably in the multi-armed bandit framework, where the objective is to minimize the cumulative regret over a sequence of tasks by incrementally transferring knowledge from prior tasks. We introduce a novel bandit algorithm based on a method-of-moments approach for the estimation of the possible tasks and derive regret bounds for it.

1 Introduction

The paper studies transfer across sequential online-learning tasks, a setting less considered than batch transfer. It models hidden bandit tasks with a latent-variable approach and introduces an algorithm that transfers model estimates across episodes.

1 Introduction

  • Online transfer has been studied less often than transfer in batch learning, despite its relevance to learning across tasks.The paper frames this gap in the context of lifelong learning.Source: §1 · p. 1
  • Tasks are drawn from a stationary distribution over finitely many bandit models, whose identities and parameters are unknown to the learner.The learner is also not given the distribution over models.Source: §1 · p. 1
  • The method-of-moments robust tensor power method estimates the latent-variable model, consistently estimating all arm means when each arm is pulled at least three times per task.The estimates are used to transfer knowledge about the possible bandit models.Source: §1 · p. 1
  • tUCB is guaranteed to perform as well as UCB in early episodes and then approach the ideal performance when the bandit-model set is known.The paper also reports preliminary synthetic-data results confirming its theoretical findings.Source: §1 · p. 2

2 Preliminaries

The preliminaries specify a finite set of stochastic bandit models and define the sequential-transfer objective. They also introduce the moment and tensor notation used to represent and estimate the models.

2 Preliminaries

  • The setting has K arms with independent, identically distributed samples and a finite set Θ of m possible bandit models.For each model, the notation identifies each arm's mean, the best arm, and the model's best value.Source: §2 · p. 2
  • An arm gap measures the difference between an arm's mean and the best value in a model, while a model gap measures the absolute difference in that arm's means across two models.These definitions distinguish within-model suboptimality from between-model differences.Source: §2 · p. 2
  • The moment notation represents second and third moments of arm-reward realizations, with conditional independence allowing moments to be expressed using model means.The section also defines tensor mapping notation and Euclidean, Frobenius, and matrix max-norms.Source: §2 · p. 2
  • The sequential-transfer objective is to minimize pseudo-regret across J episodes, each with n steps and a task drawn from a distribution over Θ.The learner knows m, J, and n, but not the identity of the task.Source: §2 · p. 2

3 Mult-armed Bandit with Finite Models

mUCB uses a known finite set of models to narrow the plausible tasks as it observes rewards. It selects arms optimistically among compatible models, with a regret bound that can improve on UCB by focusing on fewer arms and exploiting model gaps.

3 Mult-armed Bandit with Finite Models

  • mUCB retains models whose arm means are compatible with observed estimates and uncertainty, then pulls the optimal arm of the most optimistic retained model.A model can be discarded when even one arm fails the compatibility condition.Source: §3 · p. 2
  • mUCB's expected-regret bound depends on the optimistic models and arms, and its regret is never worse than UCB and is often significantly smaller.The theorem states its bound for a model set containing the actual model.Source: §3 · p. 3
  • With high probability, mUCB does not discard the actual model and can discard more optimistic models until the actual model's optimal arm is pulled for the remainder.The resulting bound depends on the arms optimal for optimistic models, a subset of all K arms.Source: §3 · p. 3
  • The model-gap terms can exceed the corresponding arm gaps, providing a further source of improvement over UCB.The paper also notes that mUCB focuses on a restricted set of arms.Source: §3 · p. 3

4 Online Transfer with Unknown Models

tUCB addresses sequential transfer when the set of bandit models is unknown, estimating model means across episodes and using those estimates to guide per-task bandit learning. Its regret is never worse than UCB and approaches the known-model mUCB performance as tasks accumulate.

4.1 The transfer-UCB Bandit Algorithm

  • RTP estimates model means from reward samples using second- and third-moment tensors, while umUCB uses uncertain model estimates to select optimistic arms.At each task’s start, umUCB pulls every arm three times so RTP has samples for estimating those moments.Source: §4.1 · pp. 3–4

4.2 Sample Complexity of the Robust Tensor Power Method

  • The estimation bound reduces model-count dependence from O(m^5) to quadratic in m and avoids polynomial dependence on the mean matrix’s smallest singular value.The authors note a somewhat worse dependency on σmin in their bound than in prior bounds.Source: §4.2 · p. 5

4.3 Regret Analysis of umUCB

  • umUCB never performs worse than UCB, even when uncertain estimated models could bias it toward suboptimal arms.It avoids pulling optimistic non-dominated arms that cannot be optimal for any optimistic model.Source: §4.3 · pp. 5–6
  • As the number of episodes grows, umUCB reaches mUCB-like performance once optimistic models have only one optimal arm; simulations show improvement can begin earlier.The one-optimal-arm condition is described as restrictive in practice.Source: §4.3 · p. 6

4.4 Regret Analysis of tUCB

  • tUCB’s cumulative regret grows linearly with episodes, is never worse than UCB, and approaches the performance of mUCB as tasks accumulate.The linear dependence on episode count is the cost of not knowing the current task identity.Source: §4.4 · p. 6, §4.3 · p. 6

5 Numerical Simulations

Synthetic simulations compare bandit algorithms on a five-model, seven-arm problem and examine regret and complexity as tasks accumulate. tUCB outperforms UCB and tends toward mUCB, but small model gaps slow its convergence to mUCB’s performance.

5 Numerical Simulations

  • The synthetic test uses five models and seven arms; θ1 and θ2 differ only in their optimal arms, while all models assign arm 3 the same mean.The smallest singular value is 0.0039 and Γσ is 0.0038, making model estimation difficult in this setting.Source: §5 · p. 6
  • UCB+ uses the known model set to discard arms that are never optimal in any model, then runs UCB on the remaining arms.Only five of the seven arms are optimal for at least one model in the simulation.Source: §5 · p. 7
  • mUCB performs significantly better than UCB and UCB+, and the observed improvement agrees with the derived upper bounds.The comparison averages per-episode regret over models and 200 runs.Source: §5 · p. 7, Figure 7 · p. 7
  • tUCB begins with UCB behavior and approaches mUCB as its model estimates improve, but does not reach mUCB’s performance within 5,000 episodes.The authors attribute the slower convergence to relatively small model gaps.Source: §5 · p. 7, Figure 8 · p. 7, Figure 6 · p. 7
  • As the number of tasks increases, tUCB outperforms UCB and tends to approach mUCB for every tested episode length.The reported cumulative regret is averaged over the total number of tasks.Source: §5 · p. 8

6 Conclusions and Open Questions

The paper introduces transfer in multi-armed bandits with tasks drawn from a finite set of problems, using model estimates to transfer knowledge across tasks. It also leaves open whether mUCB and tUCB make optimal exploration and cumulative-regret trade-offs.

6 Conclusions and Open Questions

  • The paper introduces transfer for tasks drawn from a finite set of bandit problems and presents mUCB, RTP, and umUCB, with regret and sample-complexity bounds.The conclusion reports preliminary numerical simulations and describes umUCB as never worse than UCB and tending toward mUCB.Source: §6 · p. 8
  • mUCB may miss useful exploration of arms that are not optimal under any model but could eliminate many models with few pulls.Whether its optimistic approach achieves an optimal exploration–exploitation trade-off is left open.Source: §6 · p. 8
  • tUCB’s per-episode regret is never worse than UCB, but its strategy may not minimize cumulative regret across episodes.For large J, early model identification could incur regret up to linear while reaching mUCB-like performance faster later.Source: §6 · p. 8

A Table of Notation

The notation table names quantities used to describe episode lengths, model and arm sets, RTP estimates, and moment-based estimation. It also defines notation for spectral transformations and active models.

A Table of Notation

  • The number of steps per episode is distinguished from the number of pulls to arm i after n steps of episode j.Source: A Table of Notation · p. 11
  • The table distinguishes the active model set at time t from the models that cannot be discarded at episode j.Source: A Table of Notation · p. 11
  • RTP notation covers estimated arm means, the estimated model after j episodes, and uncertainty in that estimate.Source: A Table of Notation · p. 11
  • The empirical second- and third-order moments are denoted separately.Source: A Table of Notation · p. 11
  • It names sets of arms optimal for at least one model in Θ′ and sets of models for which the arms in A′ are optimal.Source: A Table of Notation · p. 11
  • The table names the empirical whitening matrix, its linear transforms, and the corresponding eigenvalue and eigenvector quantities.Source: A Table of Notation · p. 11
  • It also defines the m largest eigenvalues of M2, their minimum and minimum gap, and the model sets associated with optimistic non-dominated arms.Source: A Table of Notation · p. 11

B Proofs of Section 3

The proofs show that mUCB retains the true model with high probability while restricting its pulls to arms recommended as optimal by models under consideration. They derive regret bounds through model elimination and note cases where those bounds can be loose.

B Proofs of Section 3

  • With high probability, the true model is never discarded, and mUCB pulls only arms that are optimal for at least one model in Θ.The proof uses the algorithm’s selection rule and a confidence event that keeps the true model in the active set.Source: B Proofs of Section 3 · p. 12
  • On the high-probability event, arms not optimal for any optimistic model are never pulled, as mUCB eliminates optimistic models while retaining the true model.The proof also shows that the true model’s optimal arm is pulled until the end, even if other models remain active.Source: B Proofs of Section 3 · p. 12
  • For each optimistic model, its model gap is at least the corresponding arm gap, supporting the conversion used in the final regret bound.The proof obtains the bound by controlling pulls of each optimistic model’s recommended arm before that model is discarded.Source: B Proofs of Section 3 · pp. 12–13
  • The proof uses a worst-case elimination count; when its condition fails, the analysis may be suboptimal and mUCB is expected to perform better than the bound.The count does not account for other models being discarded before the current optimistic model.Source: B Proofs of Section 3 · p. 14
  • The fixed-confidence hypothesis-testing alternative offers only mild improvement over UCB and matches UCB’s performance when Γmin = 0.Its identification time depends inversely on Γmin, so short identification time relative to n is needed for significant improvement.Source: B Proofs of Section 3 · p. 14

C Sample Complexity Analysis of RTP

This section completes the RTP analysis by deriving sample-complexity bounds for estimating model means. The proof combines moment-estimation concentration bounds with perturbation results for the tensor decomposition and inverse transformation.

C Sample Complexity Analysis of RTP

  • The analysis supplies a sample-complexity bound on the ℓ2 error of the estimated model means, complementing prior tensor perturbation bounds.The prior bounds controlled eigenvector and eigenvalue errors but did not give a sample-complexity bound for the mean estimates.Source: C Sample Complexity Analysis of RTP · p. 14
  • The proof bounds tensor error using second- and third-moment estimation errors, concentrates those errors, then bounds the inverse transformation to the mean estimates.The moment-error bounds use concentration arguments, including Azuma’s inequality and a union bound.Source: C Sample Complexity Analysis of RTP · pp. 14, 16, 18
  • The perturbation argument also covers repeated eigenvalues by bounding the difference between the corresponding eigenspaces.The passage states that Wedin’s result applies to this eigenspace comparison.Source: C Sample Complexity Analysis of RTP · p. 15
  • The mean-error analysis requires the second-moment error to be at most half the minimum eigengap and the minimum eigenvalue.Under this condition, Lemma 6 bounds the tensor estimation error.Source: C Sample Complexity Analysis of RTP · p. 15

D Proofs of Section 4.3

These proofs preserve the actual model in each episode’s active set and use uncertainty and gap conditions to analyze which models and arms can be selected or eliminated.

D Proofs of Section 4.3

  • On event E, the actual model remains in the active set at every episode and step.The proof defines E using simultaneous confidence conditions over models, steps, and arms.Source: D Proofs of Section 4.3 · p. 18
  • When the number of models is on the same order as the number of arms, the logarithmic-term change relative to UCB is a negligible constant-fraction improvement.This comparison is stated for the preceding bound.Source: D Proofs of Section 4.3 · p. 18
  • The proof restricts selected arms to those recommended by an active model and establishes a UCB-like bound on their pulls.The supplied passage describes the bound as coinciding with the high-probability UCB bound on the number of pulls.Source: D Proofs of Section 4.3 · pp. 18–19
  • When uncertainty is at least half the model gap, the algorithm cannot pull an arm enough to discard that model, so it remains in the uncertain-model set.This condition is used to derive the required number of arm pulls.Source: D Proofs of Section 4.3 · p. 19

E Related Work

The related work distinguishes sequential transfer among independently specified bandit models from batch and other online multitask settings. It also compares the approach with contextual and non-stationary bandits and reviews moment-based model estimation.

Models estimation

  • Prior method-of-moments work estimates latent-variable-model parameters from empirical moments, with some methods recovering mean matrices up to column permutation and offering sample-complexity guarantees.The review also notes methods using moments through third order and excess correlation analysis for a Dirichlet-distributed mixing parameter.Source: E Related Work · pp. 19–20

Online Multi-task

  • Online multitask learning changes tasks at each step and reveals both the task identity and true label, unlike the paper’s sequential bandit setting.The cited works use samples across tasks to improve worst-case performance over treating samples separately: Dekel et al. (2006); Saha et al. (2011); Cavallanti et al. (2010); Lugosi et al. (2009).Source: E Related Work · p. 20

Contextual Bandit

  • Contextual bandits reveal the context at each step and may use similarity between contexts, whereas this setting hides task identity during repeated interaction and treats models as independent.The review cites Agarwal et al. (2012) and Langford and Zhang (2007).Source: E Related Work · p. 20

Non-stationary Bandit

  • Non-stationary UCB tracks distribution changes with a sliding window or discounting; in the paper’s task sequence its worst-case order matches UCB, though it can perform worse than tUCB outside worst-case settings.The review gives O(J√n) for T = nJ and R = J, and notes that transferring averages after a switch can introduce transfer bias.Source: E Related Work · p. 20

F Numerical Simulations

The numerical-simulations appendix reports model arm means and compares UCB, UCB+, and mUCB complexity across models and on average. It also extends tUCB performance graphs to J = 10000 for n = 5000.

F Numerical Simulations

Loading 1307.6887v1…