PaperlayerView exact revision on arXiv

Source-linked AI summary

Online Learning and Bandits with Queried Hints

Aditya Bhaskara, Sreenivas Gollapudi, Sungjin Im, Kostas Kollias, Kamesh Munagala

arXiv:2211.02703v1cs.DScs.LG

TL;DR

The paper asks whether a few pre-play probes can improve regret against the hindsight optimum. It shows that, with correct hints, k=2 probes suffice for horizon-independent constant regret bounds.

  • Problem

    Can a few pre-play probes improve regret for online learning and MAB against the best choice in hindsight?

    Source: §1.2 · p. 3

  • Method

    Before playing, query an oracle for the best of k options, then play the option it suggests.

    Source: §1.1 · p. 2

  • Results

    With correct hints, k=2 probes suffice for constant regret bounds independent of the time horizon.

    Source: §1.2 · p. 3

  • Takeaways & Limitations

    The reverse prophet inequalities are crucial to the algorithms and regret analyses, and are also standalone probability tools of independent interest.

    Source: §1.3 · p. 4

    In the AllProbe model, the regret bound depends on the number of arms worse than standard UCB bounds; improving it to O(n) remains open.

    Source: §5 · p. 14

Abstract

from arXiv · show

We consider the classic online learning and stochastic multi-armed bandit (MAB) problems, when at each step, the online policy can probe and find out which of a small number ($k$) of choices has better reward (or loss) before making its choice. In this model, we derive algorithms whose regret bounds have exponentially better dependence on the time horizon compared to the classic regret bounds. In particular, we show that probing with $k=2$ suffices to achieve time-independent regret bounds for online linear and convex optimization. The same number of probes improve the regret bound of stochastic MAB with independent arms from $O(\sqrt{nT})$ to $O(n^2 \log T)$, where $n$ is the number of arms and $T$ is the horizon length. For stochastic MAB, we also consider a stronger model where a probe reveals the reward values of the probed arms, and show that in this case, $k=3$ probes suffice to achieve parameter-independent constant regret, $O(n^2)$. Such regret bounds cannot be achieved even with full feedback after the play, showcasing the power of limited ``advice'' via probing before making the play. We also present extensions to the setting where the hints can be imperfect, and to the case of stochastic MAB where the rewards of the arms can be correlated.

1 Introduction

The paper studies online optimization and stochastic bandits, where classic regret bounds depend on the horizon, and asks whether a few pre-play queries can improve them. It develops probing models and algorithms, reports stronger regret guarantees, and situates them among related hint and bandit settings.

1 Introduction

  • Classic online optimization and stochastic bandits compete with an omniscient fixed-action benchmark, with optimal O(√T) regret dependence in online learning and unknown-distribution arms in stochastic MAB.In stochastic MAB, only the chosen arm's reward is observed after play.Source: §1 · p. 2

1.1 Probe Model and Motivation

  • The probe model asks an oracle about a few options before play, returning either the best option's identity or the probed options' rewards or losses.The paper frames this as a parsimonious machine-learning hint that the policy actively queries.Source: §1.1 · p. 2

1.2 Results and Conceptual Contribution

  • With k=2 probes, the main results give time-independent constant regret for online optimization and stochastic MAB when hints are correct.The paper also reports O(√B + 1) regret with B imperfect hints for linear and convex optimization.Source: §1.2 · p. 3
  • Probe-based directional comparisons yield constant regret for linear optimization over any domain and convex optimization over any convex space, improving on the O(ln T) result for sphere domains in.The comparison asks whether cost is increasing along a chosen direction.Source: §1.2 · p. 3

1.3 Overview and Technical Highlight

  • The analysis develops reverse prophet inequalities that bound maxima or minima of independent random variables and support both the algorithms and regret analyses.The authors identify these lemmas as probability tools of independent interest.Source: §1.3 · p. 4

1.4 Other Related Work

  • Unlike related probing work that gives the benchmark as many probes as the policy, this paper treats probes as extra power for the learner against an unprobed omniscient benchmark.The paper also distinguishes its observed-reward setting from dueling bandits, where feedback is a noisy pairwise comparison.Source: §1.4 · pp. 4–5
  • Related limited-advice experts models permit only k of m experts' predictions per round, but arbitrary predictions still leave Ω(√(nT)) regret even with all experts' advice.The paper distinguishes this from probes that compare actual options.Source: §1.4 · p. 5

2 Model and Results

The section defines probing models for online optimization and stochastic MAB, then presents regret bounds for these settings and extensions. Its results depend on how many options are probed, what feedback probing reveals, and whether hints or rewards satisfy the stated conditions.

2 Model and Results

  • BestProbe reveals the best probed option without its reward or loss value; AllProbe additionally reveals probed-arm rewards and applies only to stochastic MAB.When k=1, the models reduce to classic online linear optimization and stochastic MAB, with the same hindsight benchmark.Source: §2 · p. 6

2.1 Our Results

  • With k=2 probes, online linear optimization has horizon-independent regret; related techniques yield O(ln n) regret for experts and horizon-independent regret for online convex optimization.The section states that the dependence on T is removed for linear and convex optimization.Source: §2.1 · p. 6
  • For B imperfect hints, the authors give a B-dependent regret bound and state that its dependence on B is trivially optimal; similar results hold for online convex optimization.The supplied passage does not provide the bound’s full expression.Source: §2.1 · p. 6
  • For stochastic MAB, k=2 BestProbe gives parameter-independent O(n^2 log T) regret, while k=3 AllProbe gives O(n^2) regret independent of T.Parameter-independent means the bounds do not depend on the arms’ means or variances.Source: §2.1 · p. 6
  • With correlated rewards across arms but independence across time, AllProbe achieves ˜O(n^(8/3)T^(1/3)) regret using k=4 probes.This is the correlated-reward extension of the stochastic MAB setting.Source: §2.1 · p. 6
  • Whether probing improves the Θ(√T) regret bound for adversarial bandits in either probe model remains an open question.The section contrasts this unresolved case with the stochastic MAB results.Source: §2.1 · p. 7

3 Online Linear Optimization in the BestProbe Model

Two probes make online linear optimization regret independent of the horizon, and the approach extends to convex domains and experts. The section also addresses hints that are incorrect on some rounds.

3 Online Linear Optimization in the BestProbe Model

  • Two probes yield horizon-independent regret for online linear optimization; the results extend to arbitrary convex domains and logarithmic dependence on the number of experts.The experts result retains regret independent of T.Source: §3 · p. 7

3.1 Algorithm: Differentially Private Regularization

  • LwC samples two noisy regularized optima, probes which has lower loss, and plays that option.The analysis uses differentially private noise so the better of two samples based on past losses matches the expected performance of an optimum based on current losses.Source: §3.1 · p. 8

3.2 Analysis

  • A reverse prophet inequality bounds the expected minimum loss of two regularized optima by the expected loss of the current-loss optimum.This comparison lets the algorithm's expected per-step loss be bounded by the hypothetical Be the Regularized Leader algorithm.Source: §3.2 · pp. 9–10

3.3 Handling Imperfect Hints

  • The imperfect-hint guarantee depends on the number of incorrect hints, and this dependence is optimal for any horizon.The stated extremes are O(T) regret when all hints are incorrect and recovery of Theorem 1 when none are incorrect.Source: §3.3 · p. 10
  • With imperfect hints, the algorithm uses the hinted action with probability 1 − p and otherwise follows the regularized action; it tracks errors to support unknown error counts.The doubling trick handles an unknown number of incorrect hints.Source: §3.3 · p. 10

4 Stochastic MAB in the BestProbe Model with k = 2 Probes

In the BestProbe stochastic bandit model, two probes give a parameter-independent regret bound. Meta UCB-V and reverse-prophet inequalities underpin the guarantee.

4.1 The Meta UCB-V Algorithm

  • Meta UCB-V runs UCB-V on pairs of arms, treating each pair's maximum reward as its meta-arm reward.Probing a pair reveals the maximum of their rewards, and the algorithm selects pairs using optimistic estimates.Source: §4.1 · pp. 11–12

4 Stochastic MAB in the BestProbe Model with k = 2 Probes

  • O(n^2 log T) regret is achieved with k = 2 probes in the BestProbe model.The policy learns which probed arm has the highest reward, but observes only the reward of the arm played.Source: §4 · p. 11, §4.1 · p. 12

4.2 Reverse Prophet Inequalities

  • Reverse prophet inequalities lower-bound expected pair maxima using arm means and variances, making expected regret non-positive when the relevant mean gap is small.The analysis extends the inequalities to pairs, which may be dependent even when the original arms are independent.Source: §4.2 · pp. 12–13, §4.1 · p. 12

4.3 Proof of Theorem 8

  • For each suboptimal meta-arm, the proof bounds its regret by 50 ln T, yielding the theorem's overall bound against the best-arm benchmark.The analysis compares regret against the meta-arm optimum and then relates it to regret against the best arm.Source: §4.1 · p. 12, §4.3 · p. 14

5 Stochastic MAB in the AllProbe Model

In the AllProbe model, three probes yield O(n^2) regret. The algorithm combines round-robin exploration with UCB-based exploitation, using sample-mean and variance tail bounds in the analysis.

5 Stochastic MAB in the AllProbe Model

  • One probe explores arms round-robin to update sample means and variances, while two probes select the arms with the largest UCB values.The analysis assumes the policy plays one of the two exploitation-probed arms, not the exploration-probed arm.Source: §5 · p. 14
  • O(n^2) regret is achieved in the AllProbe model with k = 3 probes.The policy receives the rewards of all probed arms at each step.Source: §5 · p. 14
  • The O(n^2) bound has worse dependence on the number of arms than standard UCB bounds; improving it to O(n) remains open.The paper also leaves constant regret for simply playing the two highest-sample-mean arms as an open question.Source: §5 · p. 14

5.1 Some Tail Bounds

  • The analysis assumes arm rewards lie in [0, 1] and uses tail bounds for sample means and variances after exploration probes.These bounds are attributed to Audibert et al.Source: §5.1 · p. 15

5.2 Proof of Theorem 11

  • When a suboptimal arm's gap is small relative to its variance, the pair's expected regret is non-positive; otherwise, regret decays exponentially over time.The proof combines these cases with an O(n) cost for the first 4n steps to obtain the stated bound.Source: §5.2 · pp. 15–16

6 Handling Correlation Between Arms in the AllProbe Model

For i.i.d. correlated rewards in the AllProbe model, the independent-arm analysis does not apply, so the paper uses a different algorithm and analysis. With four probes, it obtains a regret bound with sublinear dependence on the horizon.

6.1 Correlation-Exploitation Algorithm

  • The algorithm explores every arm pair round-robin to estimate means and pairwise gains, then probes the highest-mean arm and its estimated best partner.It uses two explore and two exploit probes per step.Source: §6.1 · p. 17

6.2 Analysis

  • With k=4 probes, the correlation-exploitation algorithm achieves parameter-independent regret eO(n^8/3 T^1/3) for correlated rewards.This dependence on T cannot be achieved in the standard bandit model with k=1 probes.Source: §6.2 · p. 17, §6 · p. 17
  • An optimal partner can offset an arm’s reward gap in expectation, while estimation error leaves expected regret bounded by ∆i − Di(t).For every arm i, some j has Gji ≥ ∆i; if that partner is identified, playing the pair incurs zero expected regret.Source: §6.2 · p. 18
  • Round-robin pair sampling supplies at least t/n^2 gain samples per pair, and the analysis shows the excess regret term shrinks with time.The proof bounds the probability that ∆i − Di(t) remains large using concentration bounds.Source: §6.2 · pp. 18–19

6.2.1 Tight Instance

  • A constructed three-arm instance makes the analysis tight: the algorithm incurs Ω(n/∆) regret, while any pair-playing strategy has nonnegative expected regret at each step.The instance adds n−3 dummy arms with zero reward.Source: §6.2.1 · pp. 19–20

7 Conclusion

The conclusion identifies unresolved questions about the stochastic assumptions behind the MAB results and the strength of two probes. It also points to imperfect hints and contextual bandits as directions for further work.

7 Conclusion

  • Whether MAB improvements require stochastic assumptions remains open; the paper makes progress with correlated MAB results but says those results may be improved.The authors ask whether improved regret guarantees are possible for adversarial MAB.Source: §7 · p. 20
  • Whether k=2 probes yield constant regret in the AllProbe model remains open, and no T-dependent lower bound is known for k=2 in either probe model.The cited O(n^2 log T) bound does not resolve whether its log T dependence is necessary.Source: §7 · p. 20
  • The paper proposes extending bandit results to imperfect hints and exploring probes in linear contextual bandits with low-dimensional latent variables.The contextual-bandit question is whether multiple probes improve regret bounds.Source: §7 · p. 20

A Extension to Experts and Online Convex Optimization

This section extends the paper’s results to experts and online convex optimization, with a sharper experts guarantee and a stated extension to imperfect hints.

A Extension to Experts and Online Convex Optimization

A.1 Experts Setting: Logarithmic Regret

In the experts setting, Hedge with Choice uses two probes to select between arms and achieves logarithmic regret. Its analysis relates its guarantee to that of the BtRL algorithm.

A.1 Experts Setting: Logarithmic Regret

  • The algorithm samples from a Gumbel distribution, making LwC a modification of classical Hedge.The Gumbel scale is 1/η, with η constant in the stated range.Source: §A.1 · pp. 24–25
  • HwC independently samples two arms from its distribution, probes to identify the lower-loss arm, then plays it and incurs that loss.The setting subsequently reveals all arms’ losses for the step.Source: §A.1 · pp. 24–25
  • The proof bounds HwC regret by the BtRL algorithm’s regret, then applies the BtRL bound to obtain the experts theorem.The analysis uses the Gumbel distribution and sets D=2 for the unit-simplex vertices.Source: §A.1 · p. 25
  • For experts, HwC with constant η ∈(0, 0.4] has regret O(ln n).The theorem states the bound for the experts setting.Source: §A.1 · p. 25

A.2 Online Convex Optimization

The section adapts the probing framework to online convex losses by comparing two regularized outcomes before choosing an action. It relates the resulting regret to a base algorithm and recovers a stated regret bound for online linear optimization.

A.2 Online Convex Optimization

  • The setting assumes W is closed, convex, and compact in [−1, 1]^d, with obliviously generated losses whose gradient norm is bounded by β and Hessian eigenvalues by γ.Source: §A.2 · p. 25
  • CwC chooses between two probed points by comparing their losses, then plays the point with lower loss and learns the loss function.The points are computed as regularized optima using independent draws from the same Gamma distribution.Source: §A.2 · pp. 25–26
  • The analysis bounds CwC regret by BtRL regret using an η-differential-privacy property, then combines that comparison with a BtRL regret lemma.The cited passages do not give the full regret expressions.Source: §A.2 · p. 26
  • For online linear optimization with each ℓt in [0, 1]^d, β ≤ d and the section recovers a ˜O(d^2) regret bound from Theorem 1.The theorem’s bound for the broader convex setting is not fully specified in these passages.Source: §A.2 · p. 26

B Concentration Bounds

This section states a Chernoff-bound result for independent random variables supported on [0, 1], defining their expectations and their summed expectation before presenting the bounds.

B Concentration Bounds

  • The paper says its proofs use standard Chernoff bounds and states the version used for completeness.Source: B Concentration Bounds · p. 26
  • The stated concentration result concerns independent [0, 1]-supported variables Xi, with pi = E[Xi] and μ defined as the sum of the pi values.The actual inequalities that follow are not included in these passages.Source: B Concentration Bounds · p. 26

B.1 Proof Sketch of Theorem 12

The proof sketch of Theorem 12 derives concentration bounds for sample means and variances, adapting results from through parameter substitutions.

B.1 Proof Sketch of Theorem 12

  • The proof maps its notation to and omits the subscript t from mi, Vi, and si.Source: §B.1 · p. 27
  • The sample-mean bound follows Eq. (48) in, using n = t and si ≤ n; Lemma 23 gives a probability statement for |µi − mi|.The bound’s right-hand side is not fully specified in these passages.Source: §B.1 · p. 27
  • The proof establishes the first part of Theorem 12 and notes that a similar bound holds for the sample variance.Source: §B.1 · p. 27
  • For the second part of Theorem 12, the proof bounds Vi using Lemma 25 and then applies Eq. (50) in with specified parameter substitutions.The text identifies x = 0.01σi^2/si, n = t = si, and L = nx/t^2.Source: §B.1 · p. 27
Loading 2211.02703v1…