Adversarial Bandit Optimization with Globally Bounded Perturbations to Linear Losses

Dimensions overall score 2.0

• The SCRiBLe algorithm maintains a sequence {xt}T t=1⊂K, which is updated according to xt+1 = arg min x∈K {η ∑t τ=1 g⊤τ x +R(x)}.method 90%
  Evidencepartial

  The algorithm maintains a sequence {xt}T t=1⊂K , which is updated according to xt+1 = arg min x∈K { η ∑t τ =1 g⊤ τ x +R(x) }

  Implicationpartial

  This is a direct description of the SCRiBLe algorithm's update rule, explicitly stated in the text.

  Verificationpartial

  partial

• SCRiBLe utilizes a ν-self-concordant barrier R, which always exists on the action set K.method 90%
  Evidencepartial

  SCRiBLe utilizes a ν-self-concordant barrier R, which always exists on the action setK.

  Implicationpartial

  This statement clearly defines a property of the SCRiBLe algorithm and its reliance on a specific type of barrier function.

  Verificationpartial

  partial

• The paper establishes both expected and high-probability regret guarantees for adversarial bandit optimization with globally bounded perturbations.result 95%
  Evidencepartial

  Under this model, we establish both expected and high-probability regret guarantees.

  Implicationpartial

  This is a primary result explicitly stated in the abstract and reinforced by the mention of Lemma 9's role in deriving these guarantees.

  Verificationpartial

  partial

• The analysis recovers an improved high-probability regret bound for classical bandit linear optimization as a special case.result 90%
  Evidencepartial

  As a special case of our analysis, we recover an improved high-probability regret bound for classical bandit linear optimization, which corresponds to the setting without perturbations.

  Implicationpartial

  This is a specific outcome of the general analysis, highlighted in the abstract as a notable consequence.

  Verificationpartial

  partial

• A lower bound on the expected regret is proven, complementing the upper bounds.result 90%
  Evidencepartial

  We further complement our upper bounds by proving a lower bound on the expected regret.

  Implicationpartial

  This is a key theoretical contribution mentioned in the abstract, indicating a complete picture of the regret bounds.

  Verificationpartial

  partial

• Lemma 9 is a key technical result that establishes a bound on ∑T t=1 θ⊤t xt−∑T t=1 θ⊤t x∗.technical 90%
  Evidencepartial

  The lemmas presented above collectively lead to Lemma 9, which constitutes a key technical result of this paper. In particular, it establishes a bound on ∑T t=1 θ⊤ t xt−∑T t=1 θ⊤ t x∗

  Implicationpartial

  The text explicitly labels Lemma 9 as a 'key technical result' and describes its specific mathematical contribution.

  Verificationpartial

  partial

• For any horizon T ≥ 1, there exists an adversary generating a C-approximately linear function sequence such that the regret is at least 2C.result 90%
  Evidencepartial

  Theorem 12 For any horizon T ≥ 1 and any player, there exists an adversary generating a C-approximately linear function sequence such that the regr et is at least 2C.

  Implicationpartial

  This is a specific lower bound result presented as Theorem 12, with clear conditions and outcome.

  Verificationpartial

  partial

Competitive landscape

This paper theoretically analyzes adversarial bandit optimization with bounded perturbations to linear losses, providing new regret bounds.