On the Computational Tractability of Robust Bandits

What it claims

The tractable special case is linear robust bandits. Arms lie in a Euclidean ball X ⊆ R^dX and outcomes in a Euclidean ball D ⊆ R^dD. Reward is linear: r(x,y) = aᵀx + bᵀy. Each hypothesis is a set of d_C affine constraints, Cy + Bx + d = 0, that define the feasible outcome means K_h(x) for each arm. On round t:

1. The learner pulls arm x_t.
2. An adversary picks any distribution whose mean lies in K_h⋆(x_t).
3. The learner sees the outcome y_t, not just the reward.

Regret is measured against V⋆ = max_x min_{y∈K⋆(x)} r(x,y). That is the worst-case value under the true hypothesis, not the best action in hindsight.

Theorem 1 gives a policy that runs in time polynomial in the encoding size |ϕ| and T, with regret Õ(√T). The hidden factor is polynomial in the dimensions, in S⁻¹ (the transversality cutoff) and in C_r (the reward range). The exact dependence is in Theorem 21, which is not in the fetched text. Theorem 3 gives a matching Ω(√T) lower bound.

How it works

What counts as "efficient". The policy must run in time polynomial in |ϕ| and T, and its regret must be at most poly(|ϕ|)·T^(1−α) for some fixed α > 0. Merely sublinear regret does not qualify. The authors explain why: Pitt's delaying trick can turn any exponential-time sublinear learner into a "polynomial-time" one. S⁻¹ and the reward-range bound C_max are given in unary, so the bounds count as polynomial in |ϕ|.

Transversality assumption. Every hypothesis must satisfy dist(p, D) ≥ S·dist(p, K_h(x)) with S ∈ (0,1]. Informally, the constraint solution spaces must stay uniformly away from tangency with the outcome ball.

Lower bound. Stochastic linear bandits embed directly. Take D = [−1,1], r(x,y) = y, and K(x) = {θᵀx}, with S = 1. The known Ω(√T) bound for stochastic linear bandits therefore transfers.

Warm-up T^(2/3) algorithm (Theorem 4). The constraints define a subspace L = ker[d⋆ B⋆ C⋆] over vectors w = (1, x, y). The learner tracks its knowledge of L with an ellipsoid E_V rather than an exact subspace, because observations are noisy. It only needs the directions the adversary actually uses.

flowchart TD
  A[Start block] --> B{Some arm has no feasible mean in E_V?}
  B -- yes --> C[Play that arm to explore]
  B -- no --> D[Play arm with best worst-case reward]
  C --> E[Repeat arm n rounds, average outcome]
  D --> E
  E --> F{Average inside E_V?}
  F -- no --> G[Enlarge ellipsoid]
  F -- yes --> A
  G --> A

Each block repeats one arm for n rounds. The feasible-mean sets are conservative, so the arm values are optimistic. Regret is Õ(n + T/√n), and n = ⌈T^(2/3)⌉ gives Õ(T^(2/3)). At this stage the paper assumes the arm-selection step can be computed exactly. Its computational cost is deferred.

Limits

• Truncated text. The fetched page ends partway through the warm-up proof. It does not include:
• the Õ(√T) algorithm itself,
• how the arm-selection optimisation is made polynomial-time,
• which generalisations are NP-hard.

The reader has to open the paper for those parts.

• Narrow tractable case. Results cover only Euclidean-ball arm and outcome sets, linear rewards, and affine constraints that satisfy transversality. The hidden constant grows polynomially in S⁻¹ and C_r, so near-tangent instances get expensive.
• Different benchmark. Robust-bandit regret competes with the worst-case value of the true hypothesis. The authors note this is easier than the best-in-hindsight benchmark used in partial monitoring and smoothed online learning. Their guarantees are not directly comparable to those settings.
• Learner must see outcomes. The learner observes the full outcome y_t, not only the reward.
• Authors' own framing. They describe the work as "a small step" towards efficient unrealizable learning.