PaperlayerView exact revision on arXiv

Source-linked AI summary

Conservative Contextual Linear Bandits

Abbas Kazerouni, Mohammad Ghavamzadeh, Yasin Abbasi-Yadkori, Benjamin Van Roy

arXiv:1611.06426v2stat.MLcs.LG

TL;DR

The paper asks how contextual linear bandit learning can remain safe relative to a baseline while minimizing regret. It proposes CLUCB, which applies the safety constraint over time, and reports a regret bound with a time-independent conservatism cost. The paper also extends the algorithm to unknown baseline rewards and reports experiments supporting its analysis.

  • Problem

    In contextual linear bandits, the paper studies how to minimize regret while keeping cumulative expected rewards above a fixed percentage of a baseline's at every time.

    Source: §1 · pp. 2–3

  • Method

    CLUCB plays the standard LUCB action only when it satisfies the safety constraint for the worst parameter in the confidence set, and otherwise follows the baseline.

    Source: §1 · p. 3, §3 · p. 5

  • Results

    CLUCB's regret bound adds a time-independent conservatism term to a standard linear-UCB regret term growing at rate T log(T), and the algorithm extends to unknown baseline rewards without changing its regret rate.

    Source: §1 · p. 3, §6 · p. 16

  • Takeaways & Limitations

    The paper reports that CLUCB satisfies the safety constraint with high probability while achieving a regret bound equivalent to LUCB up to an additive time-independent constant.

    Source: §6 · p. 16

    For CLUCB2, nested confidence sets can increase computational complexity, though the nesting occurs automatically after sufficient data and can then be relaxed.

    Source: §4 · p. 13

Abstract

from arXiv · show

Safety is a desirable property that can immensely increase the applicability of learning algorithms in real-world decision-making problems. It is much easier for a company to deploy an algorithm that is safe, i.e., guaranteed to perform at least as well as a baseline. In this paper, we study the issue of safety in contextual linear bandits that have application in many different fields including personalized ad recommendation in online marketing. We formulate a notion of safety for this class of algorithms. We develop a safe contextual linear bandit algorithm, called conservative linear UCB (CLUCB), that simultaneously minimizes its regret and satisfies the safety constraint, i.e., maintains its performance above a fixed percentage of the performance of a baseline strategy, uniformly over time. We prove an upper-bound on the regret of CLUCB and show that it can be decomposed into two terms: 1) an upper-bound for the regret of the standard linear UCB algorithm that grows with the time horizon and 2) a constant (does not grow with the time horizon) term that accounts for the loss of being conservative in order to satisfy the safety constraint. We empirically show that our algorithm is safe and validate our theoretical analysis.

1 Introduction

The paper studies safety in contextual linear bandits, where an algorithm should maintain performance relative to a baseline while learning. It proposes CLUCB to enforce that constraint and bound the cost of conservative exploration.

1 Introduction

  • Safety guarantees matter because deployed learning policies may perform poorly, while a safe policy is guaranteed to perform at least as well as a baseline with high probability.The paper frames this guarantee as relevant to decision-making problems across fields including online marketing, health sciences, finance, and robotics.Source: §1 · pp. 1–2
  • Offline safety learns from batch data, whereas online safety must also control intermediate performance during real-system interaction.The paper notes that online exploration can be substantial early on, motivating more conservative action selection.Source: §1 · p. 2
  • The paper studies safety in contextual linear bandits, including personalized ad recommendation, where the performance constraint must hold uniformly over time.The learner's expected cumulative rewards must remain above a fixed percentage of the baseline policy's expected cumulative rewards.Source: §1 · pp. 2–3
  • CLUCB plays the standard LUCB action only when it satisfies the safety constraint for the worst parameter in the confidence set; otherwise it follows the baseline.The constraint's fixed percentage reflects the risk the manager is willing to take.Source: §1 · p. 3
  • CLUCB's regret bound combines a standard LUCB term growing at rate T log(T) with a time-independent term for conservative behavior.The paper contrasts this constant conservatism cost with the time-growing cost in the MAB bound of.Source: §1 · p. 3
  • The paper extends CLUCB to unknown baseline rewards without changing its regret rate and reports experiments supporting its safety and theoretical analysis.Source: §1 · p. 3

2 Problem Formulation

The formulation places a baseline-relative performance constraint on a linear bandit learner. It specifies the bandit feedback and assumptions, then asks the learner to minimize regret while respecting that constraint at every round.

2.1 Linear Bandit

  • At each round, the learner selects an action from a possibly infinite set, with each action associated with a feature vector, and then observes a random reward.Source: §2.1 · p. 3
  • The expected reward of the selected action is r_t(a_t), and the reward noise is conditionally mean-zero with variance at most σ^2 under the stated sub-Gaussian assumption.Source: §2.1 · p. 3
  • Time-varying action sets and features include contextual bandits, where an action's feature vector is formed from the current state-action pair.Source: §2.1 · p. 4
  • The unknown parameter and feature vectors are bounded, and every action's expected reward lies in [0, 1].Source: §2.1 · p. 4
  • With the parameter unknown, the learner seeks to maximize cumulative expected rewards, equivalently minimizing regret against the optimal strategy.Source: §2.1 · p. 4

2.2 Conservative Linear Bandit

  • The conservative setting adds a baseline policy that selects an available action each round; its expected rewards are assumed known, though a later section relaxes this assumption.Source: §2.2 · p. 4
  • At every round, the baseline-agent performance gap must stay below fraction α of baseline performance; smaller α tolerates less loss and requires more conservative behavior.Source: §2.2 · pp. 4–5
  • Baseline-policy data are excluded from confidence-set construction in the known-reward case for simpler analysis, and may only estimate the unknown parameter well in a limited subspace.Source: §2.2 · p. 5

3 A Conservative Linear Bandit Algorithm

CLUCB combines optimistic linear-UCB action selection with a conservative fallback, choosing the optimistic action only when it preserves the performance constraint. Its confidence sets support high-probability safety, while its regret bound separates LUCB regret from a time-independent conservatism cost.

3 A Conservative Linear Bandit Algorithm

  • CLUCB plays the optimistic action only when it satisfies the performance constraint for every parameter in the confidence set; otherwise it follows the baseline.The optimistic action is the best-performing available action within the confidence set.Source: §3 · pp. 5–6

3.1 Construction of Confidence Sets

  • The confidence sets contain the true parameter with probability at least 1−δ, which makes the performance constraint hold at each round with that probability.The confidence set is updated after optimistic actions; baseline rewards are known, so baseline actions provide no new information about the unknown parameter.Source: §3.1 · pp. 6–7

3.2 Regret Analysis of CLUCB

  • Assumption 3 bounds the baseline gap at each round between ∆l and ∆h, where 0 ≤ ∆l ≤ ∆h, and requires a positive reward lower bound 0 < rl < rh at each round.The authors note that 1 is an obvious candidate for both ∆h and rh because mean rewards lie in [0, 1], while ∆l = 0 is a reasonable candidate.Source: §3.2 · p. 7
  • CLUCB’s regret decomposes into LUCB regret on optimistic rounds and regret from rounds when it plays the conservative baseline action.The conservative cost does not grow with the horizon, unlike the conservative-regret bound cited for the MAB setting.Source: §3.2 · pp. 7, 12
  • With probability at least 1−δ, CLUCB satisfies performance constraint (3) for every t ∈ N and has the regret bound of Theorem 6.The second term accounts for losses from conservative play and does not grow with time, since CLUCB is conservative only a finite number of times. Regret is larger for smaller α and smaller for smaller ∆h, when the baseline policy πb is closer to optimal.Source: §3.2 · pp. 11–12

4 Unknown Baseline Reward

CLUCB2 extends conservative linear UCB to unknown baseline rewards while retaining the safety guarantee and regret rate. Its confidence-set construction uses rewards from both optimistic and conservative actions, with nested sets potentially adding computation early on.

4 Unknown Baseline Reward

  • CLUCB2 checks whether to play the optimistic or baseline action using a condition chosen to satisfy the performance constraint.Source: §4 · p. 12
  • CLUCB2 builds confidence sets using rewards from both optimistic and conservative actions, and the sets contain the true parameter with high probability.Source: §4 · pp. 12–13
  • Nested confidence sets are needed for the proof and may increase computational complexity, but their constraint can be relaxed after sufficient data.Source: §4 · p. 13
  • CLUCB2 satisfies the performance constraint with high probability and has the same regret rate as CLUCB, differing from LUCB only by an additive constant.Source: §4 · pp. 13–14

5 Simulation Results

In simulations, CLUCB satisfies the performance constraint while LUCB violates it in many early rounds, especially for small α. CLUCB's per-step regret converges toward LUCB's, with convergence faster for larger α.

5 Simulation Results

  • The simulations use 100 fixed arms with four-dimensional Gaussian feature vectors and average results over 1,000 realizations.Source: §5 · p. 14
  • CLUCB follows the baseline during its initial conservative phase, keeping per-step regret constant before it converges toward LUCB; this phase shortens as α increases.Source: §5 · pp. 14–15
  • CLUCB satisfies the performance constraint for every tested α, while LUCB violates it in a significant number of the first 1,000 rounds, especially at small α.Source: Figure 2 · p. 15, §5 · p. 15
  • At round 40,000, CLUCB's per-step regret converges toward LUCB's, and convergence is faster for larger α.Source: §5 · p. 15, Figure 3 · p. 16

6 Conclusion

The paper formulates a conservative linear bandit problem and proposes CLUCB, which maintains a baseline-relative reward constraint while achieving a regret bound close to LUCB's. It also presents known- and unknown-baseline versions and reports simulations supporting the analysis.

6 Conclusion

  • CLUCB constrains cumulative rewards at every time to remain at least a fraction of the baseline policy's performance.Source: §6 · p. 16
  • CLUCB satisfies the safety constraint with high probability and has regret equivalent to LUCB's up to an additive time-independent constant.Source: §6 · p. 16
  • The known- and unknown-baseline versions act conservatively for only finitely many rounds, with the number depending on baseline suboptimality.Source: §6 · p. 16

A Technical Details of the Proof of Theorems 5 and 7

The appendix proves technical bounds used in Theorems 5 and 7 through Lemma 8. Its argument defines an auxiliary function, locates its maximum, and uses that maximum to obtain the stated bound.

A Technical Details of the Proof of Theorems 5 and 7

B Proof of Theorem 7

The proof establishes the safety constraint when confidence sets contain the true parameter and bounds regret by separating LUCB regret from the cost of conservative play.

B Proof of Theorem 7

  • When confidence sets do not fail, CLUCB2 satisfies the constraints by checking them for the worst parameter in the confidence set at each time.The proof assumes this event holds with probability at least 1 − δ.Source: B Proof of Theorem 7 · p. 20
  • CLUCB2’s regret is decomposed into a LUCB regret term and a term for conservative play.The proof bounds the number of baseline-policy rounds independently of the time horizon.Source: B Proof of Theorem 7 · pp. 20, 24
  • CLUCB2’s confidence sets incorporate observations from baseline-policy rounds, making them tighter than LUCB’s sets based only on optimistic-action rounds.This supports the proof’s comparison of regret on optimistic-action rounds with LUCB regret over all rounds.Source: B Proof of Theorem 7 · pp. 20–21
  • The proof uses nested confidence sets to show that CLUCB2 follows the baseline policy at only a finite, time-independent number of rounds.It bounds the number of conservative rounds using an inequality whose left side grows as √n while the right side grows logarithmically.Source: B Proof of Theorem 7 · pp. 21, 23, 24

C Technical Detail Used in the Proof of Theorem 7

The technical lemma bounds positive solutions to an inequality involving a logarithm, supporting the proof’s bound on conservative rounds.

C Technical Detail Used in the Proof of Theorem 7

Related papers

Loading 1611.06426v2…