PaperlayerView exact revision on arXiv

Source-linked AI summary

Linearly Parameterized Bandits

Paat Rusmevichientong, John N. Tsitsiklis

arXiv:0812.3465v2cs.LG

TL;DR

The paper extends a bandit model to many arms whose expected rewards depend linearly on a multivariate random vector. It establishes regret and Bayes-risk bounds for this setting and develops phase-based and anytime policies.

  • Problem

    The paper studies bandit settings with many arms and seeks a policy whose regret is independent of the number of arms.

  • Method

    The paper extends the model to rewards that depend linearly on a multivariate random vector and considers a phase-based policy alternating exploration and exploitation, alongside an anytime policy.

  • Results

    The cumulative Bayes risk under an arbitrary policy is at least Ω(r √T), exceeding the O(log T) upper bound attainable when r = 1.

  • Takeaways & Limitations

    The multivariate model requires new regret and Bayes-risk bounds and policies because the earlier bounds and policies no longer apply.

  • Takeaways & Limitations

    The model includes an assumption that enables considering each arm separately but leads to policies whose regret scales with the number of arms.

Abstract

from arXiv · show

We consider bandit problems involving a large (possibly infinite) collection of arms, in which the expected reward of each arm is a linear function of an $r$-dimensional random vector $\mathbf{Z} \in \mathbb{R}^r$, where $r \geq 2$. The objective is to minimize the cumulative regret and Bayes risk. When the set of arms corresponds to the unit sphere, we prove that the regret and Bayes risk is of order $Θ(r \sqrt{T})$, by establishing a lower bound for an arbitrary policy, and showing that a matching upper bound is obtained through a policy that alternates between exploration and exploitation phases. The phase-based policy is also shown to be effective if the set of arms satisfies a strong convexity condition. For the case of a general set of arms, we describe a near-optimal policy whose regret and Bayes risk admit upper bounds of the form $O(r \sqrt{T} \log^{3/2} T)$.

1. Introduction

The paper studies linearly parameterized bandits with many arms, extending a scalar model to rewards depending on an r-dimensional random vector. It establishes matching bounds for the unit sphere and develops policies for strongly convex and arbitrary compact arm sets.

  • Motivation: Large-arm bandit policies should exploit reward correlation rather than treating each arm independently, because independent-arm methods require trying every arm and incur regret that grows with arm count.The paper targets policies whose regret is independent of the number of arms.
  • Model: The model assigns each arm an expected reward linear in an r-dimensional random vector Z, with r ≥ 2, so mean rewards are not perfectly correlated.This extends an earlier scalar model in which all arm means depend on one random variable.
  • Main results: For unit-sphere arms, arbitrary policies have cumulative Bayes risk at least Ω(r√T), exceeding the O(log T) upper bound attainable in the scalar case.The lower bound demonstrates that the multivariate extension is fundamentally different from the earlier r = 1 model.
  • Main results: A phase-based policy alternating exploration and exploitation achieves matching bounds for the unit sphere and remains effective when the arm set satisfies strong convexity.The paper identifies a connection between strong convexity of the arm set and phase-based policy effectiveness.
  • Main results: For arbitrary compact arm sets, an active exploration policy using least-squares estimation and confidence regions obtains regret and risk bounds O(r√T log^{3/2} T).The bound is within a logarithmic factor of the lower bound.
  • Finite arm sets: For finite fixed arm sets, the active exploration policy has regret and risk increasing as log T and log^2 T, respectively, and is within a constant factor of the asymptotic lower bound.These results describe the policy’s behavior in the finite-arm setting.

2. Lower Bounds

For unit-sphere arms, the paper establishes lower bounds for regret and Bayes risk under arbitrary policies. The analysis links cumulative risk to exploration and estimation error, showing that insufficient exploration produces large estimation errors.

  • Theorem 2.1 establishes lower bounds on regret and Bayes risk for arbitrary policies when the arms form the unit sphere.
  • The proof fixes an arbitrary policy and analyzes its history, least-mean-squares estimator, and orthogonal exploration directions.
  • For the unit sphere, the best arm for any reward vector is aligned with that vector, so its maximum expected reward equals the vector norm.
  • Cumulative risk is bounded below by the sum of squared estimation error and total exploration over the preceding periods.
  • Little exploration implies large estimation errors, providing the complementary mechanism needed for the lower-bound argument.

Appendix A.1.

The appendix develops a lower-bound argument by controlling the norm of Z and bounding directional estimation risk. It then combines these ingredients to prove the theorem.

  • Lower-bound lemmas: The proof uses Lemma 2.4 to lower-bound the probability that θ ≤∥Z∥≤β.The constants θ, β, and η are selected later to obtain the desired bound.
  • Lower-bound lemmas: Lemma 2.5 gives a lower bound on minimum directional risk for directions k = 1, . . . , r −1 when T ≥r2.The proof treats the random norm ∥Z∥ by restricting it to a suitable interval.
  • Proof strategy: The argument conditions on the history and uses the normal distribution of the relevant quantity to control the lower-bound event.The standard normal cumulative distribution function Φ is used in this probability calculation.
  • Theorem conclusion: Theorem 2.1 follows by combining Lemmas 2.2 and 2.5 and using r ≥2, which implies r −1 ≥r/2.The resulting lower bound concerns squared estimation error and minimum cumulative Bayes risk along a direction.

3. Matching Upper Bounds

This section introduces PEGE, which alternates exploration and greedy exploitation using OLS estimates. Under smooth best-arm response, it obtains matching regret and risk upper bounds for strongly convex arm sets.

  • Assumptions: The assumptions constrain error tails, arm magnitudes, and the availability of r linearly independent exploration arms.These conditions keep rewards controlled and make OLS estimation possible during exploration.
  • PEGE policy: PEGE alternates r-period exploration phases with c-period exploitation phases across cycles.Exploration plays r linearly independent arms, while exploitation repeatedly plays the greedy arm based on the OLS estimate.
  • PEGE policy: The greedy decision is G(c) = arg maxv∈Ur v′bZ(c), with ties broken arbitrarily.The estimate bZ(c) is computed from rewards observed during prior exploration phases.
  • Smooth best-arm response: SBAR(J) requires a unique best arm for every nonzero vector and a smooth response of the best arm to normalized vectors.The condition corresponds to strong convexity of the compact arm set; examples include the unit ball and suitable ellipsoids.
  • Upper bounds: Under Assumption 1 and SBAR(J), Theorem 3.1 provides regret and risk upper bounds with constants depending on σ0, ¯u, λ0, and J.The theorem applies for z ≠0 and T ≥r, with an additional bounded-moment condition used for the Bayes-risk conclusion.
  • Upper bounds: The PEGE performance bound does not deteriorate with the norm of z, despite the trivial regret bound scaling as 2¯u ∥z∥T.The result combines the theorem with the norm-based trivial bound.

Appendix A.2.

The appendix verifies the technical ingredients behind the upper bounds, including small mass near the origin, estimator control, normalized-vector stability, and greedy-regret bounds.

  • Distributional conditions: Lemma 3.2 establishes a small-mass-near-the-origin property for ∥Z∥ under the stated distributional conditions.The appendix also gives sufficient density and Gaussian conditions for bounding E[1/∥Z∥].
  • Specialization: For unit-sphere arms with standard-normal errors, Assumption 1 and SBAR(1) hold, so Theorem 3.1 yields the corresponding regret and risk bounds.The covariance choice Ir/r is included among the distributions satisfying the required moment conditions.
  • Technical lemmas: Lemma 3.4 supplies an upper bound on the squared norm difference used in the proof of Theorem 3.1.The result is obtained by taking conditional expectations given Z = z.
  • Technical lemmas: Lemma 3.5 bounds the difference between normalized vectors by the difference between the original vectors.The definition 0/∥0∥ uses a fixed unit vector, and the proof handles zero vectors separately before applying symmetry and the triangle inequality.
  • Theorem proof: The PEGE proof sums exploration and exploitation regret across cycles and then takes expectations using bounds on E[∥Z∥] and E[1/∥Z∥].Exploration contributes at most 2 ¯u r ∥z∥ per cycle, while exploitation uses the greedy-regret bound.

4. A Policy for General Bandits

The paper introduces the UE policy for arbitrary bandit problems, addressing cases where PEGE may fail because small estimation errors can strongly change the greedy arm. UE explores and exploits every period and is anytime.

  • Comparison with PEGE: When estimation error is small, greedy-decision instantaneous regret can be of the same order as ∥Z−bZ(c)∥.Under smoothness, the paper explains that the regret bound improves, enabling separation of exploration and exploitation.
  • Motivation: PEGE may be ineffective for finite or arbitrary compact arm sets because small estimation errors can disproportionately change the greedy arm.Such changes can lead to large instantaneous regret.
  • UE policy: The Uncertainty Ellipsoid (UE) policy applies to any bandit problem at the cost of slightly higher regret and Bayes risk.Unlike PEGE, UE combines active exploration and exploitation in every period.
  • UE properties: UE has an anytime property because it does not require prior knowledge of the time horizon T.The policy also permits the random vector Z and the errors to be unbounded.
  • Results: The section states regret and Bayes-risk bounds for UE and provides a detailed policy description with proofs available later in the paper.The supplied passage identifies these bounds but does not include their complete expressions.

Appendix B.

This appendix develops the UE policy and establishes regret and risk bounds for general compact, finite, and polyhedral arm sets.

  • Uncertainty Ellipsoid (UE): The UE policy initializes with r linearly independent arms, then repeatedly selects an arm maximizing estimated reward over an uncertainty ellipsoid.It updates the OLS estimate, ellipsoid, and arm-specific uncertainty radius after each observed reward.
  • Uncertainty Ellipsoid (UE): The UE index combines estimated reward with an uncertainty bonus, enabling simultaneous exploitation and exploration while accounting for correlated rewards.For independent standard basis arms, it agrees up to scaling with the classical upper confidence bound.
  • General Compact Sets of Arms: Theorem 4.1 shows that UE is nearly optimal for arbitrary compact arm sets, with regret and risk upper bounds within a logarithmic factor of lower bounds.The proof uses large-deviation inequalities for adaptive least-squares estimators.
  • Finitely Many Arms: For finitely many arms, UE achieves regret growing as log T and risk growing as log^2 T, and is asymptotically optimal within a constant factor.The result compares with lower bounds established by Lai and Robbins and Lai.
  • Polyhedral Sets of Arms: For polyhedral arm sets, reducing optimization to extreme points yields regret bounds depending on the number of extreme points, including O(r log T) in a 2r-point example.An O(r√T) polyhedral regret bound without an additional logarithmic factor remains open.

5. Conclusion

The paper studies linearly parameterized bandits with correlated arm rewards and proposes policies tailored to smooth best-arm responses and general arm sets. It obtains optimal or near-optimal regret and risk guarantees, while identifying remaining dependence and modeling limitations.

  • 5. Conclusion: The model lets each arm’s expected reward depend linearly on an unobserved r-dimensional random vector and allows correlations among arm rewards.The formulation assumes the expected-reward vector lies in an r-dimensional subspace spanned by known basis functions.
  • 5. Conclusion: For a smooth best arm response, an exploration–exploitation policy is optimal, while the general-bandit policy performs active exploration every period.These policies address different structural settings for the arm set.
  • 5. Conclusion: For finitely many arms, the policy achieves asymptotically optimal regret and risk over time but scales with the square of the number of arms.Improving this dependence remains an open question.
  • 5. Conclusion: Extending the analysis to unknown basis functions could broaden applicability, and more general correlation structures remain of interest.These are stated as directions for extending the work.

A.1 Proof of Lemma 2.4

This proof establishes probability bounds for the norm of a suitably scaled multivariate normal vector using chi-square representations and elementary inequalities.

  • A.1 Proof of Lemma 2.4: A standard normal vector’s squared norm has a chi-square distribution with r degrees of freedom, enabling bounds on Pr{θ ≤ ∥Z∥ ≤ β}.The proof applies Markov’s inequality after relating Z to a standard multivariate normal vector.

A.2 Proof of Lemma 3.2

This proof bounds E[1/∥Z∥] for a scaled multivariate normal vector by transforming the problem to chi and chi-square distributions.

  • A.2 Proof of Lemma 3.2: The proof represents Z as Y/√r for a standard multivariate normal vector and evaluates inverse-norm expectations using chi-square densities.The Gamma-function recurrence and a chi-square distribution with r−2 degrees of freedom complete the calculation.
  • A.2 Proof of Lemma 3.2: The resulting inverse-norm bound is established for r ≥ 3.The proof concludes that E[1/∥Z∥] satisfies the desired upper bound.

B. Proof of Theorems 4.1 and 4.2

The proofs extend concentration tools to adaptive linear bandits, including settings with finitely or infinitely many arms. These results support the uncertainty-ellipsoid bounds used in the main theorems.

  • Adaptive least-squares estimators are analyzed using large deviation inequalities that accommodate unbounded error variables.These inequalities are used in proving Theorems 4.1 and 4.2.
  • The finite-arm argument applies a union bound over possible arm-count configurations and ordered pairs of the selected arm and confidence matrix.The number of possible configurations is bounded using the finite arm-set size and time horizon.
  • A Chernoff inequality is extended from finitely many arms to infinitely many arms under Assumption 1.The finite-arm result is insufficient when the number of arms is infinite, motivating the extended theorem.
  • The proof combines ratio tail bounds, martingale inequalities, and a covering argument on the unit sphere to establish matrix concentration.A finite covering reduces control over all sphere directions to finitely many vectors, after which a union bound is applied.
  • The resulting concentration controls uncertainty ellipsoids and enables the regret bound for adaptive, history-dependent arm choices.The proof relates positive semidefiniteness of a block matrix to a bound involving the least-squares estimation error.

B.2 Bounds for General Compact Sets of Arms: Proof of Theorem 4.1

For general compact arm sets, the proof controls estimation error and instantaneous regret through uncertainty radii, then bounds cumulative uncertainty with a recursive argument and an auxiliary optimization problem.

  • Estimation and instantaneous regret: Large deviation inequalities bound the probability of a large estimation error and consequently the probability of large instantaneous regret.The uncertainty radius is chosen so that overestimation probabilities decay at a summable rate.
  • Regret decomposition: The regret decomposition separates initialization, large-regret events, and small-regret events controlled by the uncertainty norm.Initialization contributes O(r), while later periods are handled through the instantaneous-regret bound.
  • Exploration interpretation: The weighted norm of the selected arm measures both current regret and exploration in directions that remain insufficiently explored.Eigenvalues of the design matrix encode how frequently directions have been explored.
  • Recursive control: Large past weighted regrets imply a small current weighted norm, yielding a recursive relationship for controlling cumulative uncertainty.This relationship motivates bounding the associated optimization problem V*(c, t).
  • Auxiliary optimization: V*(c, t) is bounded by 2c0(r log c0 + (r + 1) log(r + t + 1)), where c0 = max{1, c}.This auxiliary bound is combined with the regret decomposition to obtain the theorem’s general-arm regret bound.
  • Theorem 4.1: The proof concludes with Regret (z, T, UE) ≤ 2ū(r + 2)||z|| + 2α√[2A0{r log A0 + (r + 1) log(T + 1)}].The constants a4 and a5 depend only on σ0, ū, and λ0.

B.3 Bounds for Finitely Many Arms: Proof of Theorem 4.2

The finite-arm proof completes the risk analysis by bounding how often each arm is selected, using the uncertainty-radius deviation bound and monotonicity of arm counts.

  • The expected number of selections of any arm satisfies E[N_u(z, T) | Z = z] ≤ 6 + 4α^2|U_r| log T.This bound is established for fixed z and arm u.
  • The argument uses the nondecreasing nature of N_u(z, t) together with the probability bound for large uncertainty-radius deviations.Summing the resulting tail probabilities controls expected arm counts over the horizon.
  • The proof then applies the resulting arm-count control to complete Theorem 4.2’s bound.The final step also uses the Sherman–Morrison formula and the arm regret bound.
Loading 0812.3465v2…