PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Computational Tractability of Robust Bandits

Vanessa Kosoy, Vinayak Pathak

arXiv:2610.08740v1cs.LG

TL;DR

Unrealizable learning remains difficult beyond supervised learning, and robust bandits provide an alternative framework for it. This paper identifies a special case with a polynomial-time learner and shows that small generalizations become computationally intractable.

  • Problem

    Agnostic guarantees for unrealizable learning are difficult beyond supervised learning, while robust bandits had lacked computational guarantees.

    Source: §1 · pp. 1–2

  • Method

    The paper studies robust bandits, where hypotheses partially specify the environment and an adversary chooses among consistent environments.

    Source: §1 · p. 2

  • Results

    A special case admits a polynomial-time learner, while minor generalizations quickly lead to computational intractability.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The special case marks a boundary of tractability for the robust-bandit settings considered.

    Source: §1 · p. 2

    Which other hypothesis classes admit efficient learners, and whether natural oracles can guarantee efficiency, remain open questions.

    Source: §7 · p. 12

Abstract

from arXiv · show

Learning when the environment does not belong to the learner's hypothesis class is typically handled using agnostic learning guarantees. However, for anything beyond supervised learning, agnostic guarantees are difficult to come by. Recently, imprecise bandits (Kosoy, 2025) (later renamed to robust bandits in Appel and Kosoy, 2025) were introduced as another approach to unrealizable learning in the bandits setting and a $\Theta(\sqrt{T})$ regret learner was shown for a large class. However, no computational guarantees were provided. In this paper we identify a special case that admits a polynomial-time learner with $\tilde{O}(\sqrt{T})$ regret. We also show that several small generalizations of this special case are NP-hard thus indicating that the special case is at the boundary of what is tractable. It has been recently suggested (Kosoy, 2018) that computationally efficient learners for unrealizable learning problems are crucial for solving the AI alignment problem. This work is a small step in that direction.

1 Introduction

The paper studies unrealizable learning in the context of AI alignment, where realizability may fail in multiagent settings. It analyzes robust bandits, identifying a tractable special case and small generalizations that become computationally intractable.

1 Introduction

  • Realizability can fail when agents interact: a low-regret strategy against all strategies in H may itself lie outside H, creating a grain-of-truth problem.The grain-of-truth problem is described as finding a natural class H whose learner lies within H; it remains open despite recent progress using reflective oracles [28] [54] [81].Source: §1 · pp. 1–2
  • Agnostic guarantees are difficult beyond supervised learning, and large or infinite policy classes make agnostic bandit regret problematic.The cited bandit discussion notes impossibility results for infinite policy classes and regret growing with the square root of class size for finite classes.Source: §1 · p. 2
  • Robust bandits retain a known hypothesis class containing the ground truth, but each hypothesis only partially specifies the environment, leaving an adversary to choose a consistent environment.The learner competes with the optimal strategy that knows the true hypothesis but not the adversary's choices.Source: §1 · p. 2
  • A special case of robust bandits admits a polynomial-time learner, while minor generalizations quickly become computationally intractable.The framework is presented as an alternative to agnostic learning in unrealizable settings.Source: §1 · p. 2

2 Setting

This section defines robust bandits and formalizes computational efficiency for parameterized instances. It specializes the model to linear constraints and states a tractability result and a matching-in-order dependence on the horizon.

2 Setting

  • A robust bandits instance is (X, D, H, r): arms and outcomes have possible sets, hypotheses map arms to outcome distributions, and the reward is known.A credal set is a nonempty closed convex set of distributions; the value of an arm under a hypothesis is its minimum expected reward over that hypothesis's distributions.Source: §2 · pp. 2–3
  • The game hides the true hypothesis h* from the learner, who seeks sublinear regret for every h*; statistical efficiency is defined by existence of such a learner.The learner knows the instance and horizon, while the adversary selects h* at the beginning.Source: §2 · pp. 2–3

2.1 Linear Robust Bandits

  • The linear specialization uses Euclidean-ball arm and outcome sets, linear rewards, and hypotheses defined by affine constraints on feasible outcomes.The feasible sets must be nonempty and satisfy a transversality condition with cutoff S; numerical parameters are rational and explicitly encoded.Source: §2.1 · pp. 3–4
  • For linear robust bandits, a learner achieves computational efficiency, with hidden regret factors depending polynomially on the dimensions, S^-1, and the reward range.The formal efficiency criterion requires polynomial running time in the parameter encoding length and T, and regret at most poly(|ϕ|) T^(1−α) for fixed α > 0.Source: §2 · p. 3, §2.1 · p. 4
  • The horizon dependence of the linear robust-bandit regret is tight up to logarithmic factors, because the class contains stochastic linear bandits as a special case.The lower bound is transferred from stochastic linear bandits.Source: §2.1 · p. 4

3 Related work

The related-work discussion situates robust bandits among models of imprecise beliefs, partial specifications, feedback, and restricted adversaries. It distinguishes these models by their feedback or regret benchmarks.

Imprecise probabilities and credal sets

  • Credal sets represent beliefs as closed convex sets of distributions, and robust bandits generalize stochastic bandits using imprecise probabilities.The discussion relates this approach to Levi's credal sets [56, 57] and Walley's theory of imprecise probability [80].Source: §3 · p. 5

Partial specifications of the environment

  • Partial concept classes and set-valued label hypotheses also model incomplete specifications; robust bandits adapt this idea to bandit learning.In the framework of Pour, Mansouri, and Ben-David [69] and Kosoy [52], the learner guesses a label from each hypothesis's set and is compared against the true hypothesis without knowing the adversary's label choice.Source: §3 · p. 5

Outcome feedback

  • Unlike partial-monitoring and Foster et al. [30] feedback models, robust bandits reveal the outcome and compare regret against the true hypothesis's worst-case value.Those other models compare against the best action for the true environment or the best fixed action in hindsight.Source: §3 · p. 5

Smoothed analysis and smoothed adversaries

  • Smoothed adversaries are a special case of robust bandit adversaries, but their credal set is known and their regret benchmark is the best hypothesis in hindsight.In smoothed online learning, the restriction can make learning as easy as statistical learning and can permit efficient learning with a hypothesis-class optimization oracle [12].Source: §3 · p. 5

4 Warmup: A T 2/3 Learner

The warmup learner represents information about feasible outcome means with an expanding ellipsoid and analyzes regret by block type. The computational section turns arm selection into polynomial-time optimization and uses a penalty-based stopping rule to improve exploration blocks.

4 Warmup: A T 2/3 Learner

  • The learner encodes its uncertain knowledge of the true subspace L with an ellipsoid, expanding it when a block's empirical mean falls outside.It need not identify directions the adversary never uses, and blockwise observations are noisy rather than exact.Source: §4 · p. 6
  • Updates add w w^T to V, expanding the ellipsoid in the direction of new information; each update increases its volume by a constant factor.The ellipsoid's distance from the true subspace grows only by the noise in w, about 1/√n, and the volume growth explains the logarithmic update count.Source: §4 · p. 7
  • Each uninformative block has regret about √n, while an informative block has the trivial O(n) bound; there are at most O(log n) updates.The arm is chosen by maximizing its worst-case reward over the currently guessed feasible means.Source: §4 · pp. 6–7

4.1 Computational tractability

  • The computational section implements Algorithm 1 in polynomial time by converting its optimization into a QCQP with properties that permit polynomial-time solution.The inner minimization is converted to a maximization using convex duality; Bienstock's result supplies the polynomial-time algorithm.Source: §4.1 · pp. 7–9
  • A penalty score minimizes reward plus λ times the ellipsoid penalty over all outcomes, letting the learner score outcomes beyond its current feasible set.The score's regret bound applies for every outcome in D, and the learner ends a block when the observable empirical penalty reaches its threshold.Source: §4.1 · pp. 9–10
  • Monitoring the penalty allows early block termination; the regret analysis balances a per-block cost proportional to λ against a per-round cost proportional to 1/λ.The number of blocks is O(log T), and the text states a total bound of about λ log T + T/λ before choosing λ to balance the terms.Source: §4.1 · p. 10

6 NP-hardness

The section identifies several small generalizations of the linear robust-bandits instance that are computationally hard, while finite-arm cases with ball outcomes admit an Exp3 guarantee. It also shows that easy planning alone does not ensure computationally easy learning.

6 NP-hardness

  • With Euclidean-ball outcomes, a simplex arm set reduces to its vertices and Exp3 gives ˜O(√(d_X T)) regret, but a polytope with k faces is computationally hard.A simplex outcome set is also computationally hard.Source: §6 · p. 11
  • Changing the feasible-outcome constraints from bilinear to trilinear in the hypothesis makes the problem computationally hard, even when both sets are Euclidean balls.The bilinear formulation is the one assumed in Kosoy.Source: §6 · p. 11
  • Easy planning does not guarantee easy learning: the paper gives an example with computationally easy planning but computationally hard learning.The other hardness proofs first establish that planning itself is hard, then use a reduction from planning to learning.Source: §6 · p. 11

7 Discussion and open problems

The discussion leaves open which robust-bandit hypothesis classes admit efficient learners and whether the paper's techniques extend to structured-observation settings. It cautions that easy planning alone is insufficient and points to additional oracles as a possible avenue.

7 Discussion and open problems

  • The authors also leave open whether robust-bandit-style definitions and efficient learners can be developed for other learning frameworks.Source: §7 · p. 12
  • For robust bandits, identifying other hypothesis classes with efficient learners remains open; small changes to the linear instance can make planning hard, and easy planning alone is insufficient.The authors ask whether natural oracles beyond a planning oracle could guarantee efficient learning.Source: §7 · p. 12
  • Whether the paper's techniques can yield efficient learners for structured-observation settings, including robust linear bandits and tabular reinforcement learning, remains open.Appel and Kosoy [3] prove regret bounds for that setting but do not address computational efficiency.Source: §7 · p. 12

AI Disclosure

The disclosure describes AI assistance with literature research, improving an upper bound, and drafting appendix proofs, while stating that the main body is largely human-written.

AI Disclosure

  • The authors say they mostly proved the NP-hardness results and ˜O(T^2/3) upper bound, with some GPT help finding literature; GPT 6 Astra later improved the upper bound to ˜O(√T).Source: AI Disclosure · p. 12
  • GPT 6, Fable 5.1, and Opus 5.5 helped with writing; the main body is largely human-written, while AI drafted appendix proofs from author notes and guidelines through iterative feedback.Source: AI Disclosure · p. 12

A Regret analysis of the T 2/3 learner

The regret analysis combines a bound on the number of updates with a guarantee for feasible outcomes and a bound on block regret. Its proof also uses simultaneous concentration over intervals and matrix control across updates.

A Regret analysis of the T 2/3 learner

  • The proof bounds the distance of maintained uncertainty sets from L using a matrix inequality after updates, with block-average noise controlled simultaneously over intervals.Lemma 13 establishes simultaneous concentration over intervals; Lemma 14 then controls the matrix after any number of updates.Source: A Regret analysis of the T 2/3 learner · p. 19
  • Theorem 15 bounds high-probability regret using a term proportional to n per update and a T√n term; expected regret adds at most C_rTδ.The same expression bounds regret on the stated high-probability event.Source: A Regret analysis of the T 2/3 learner · pp. 20–21
  • The number of updates is at most q(4 + 2 log2 n), independent of the horizon T.The proof bounds the count through the logarithm of the ratio between final and initial ellipsoid volumes.Source: A Regret analysis of the T 2/3 learner · p. 20
  • Whenever y lies in the learner's feasible set, the reward is at least v⋆(x) − G_BT√n.This lower bound supports the block-regret argument for blocks without updates.Source: A Regret analysis of the T 2/3 learner · pp. 20–21

A.1 Computational tractability and finite-precision implementation

This section formulates arm selection as QCQPs and develops polynomial-time approximate procedures, including a finite-precision learner that retains the stated regret rate. It completes the blockwise regret analysis by deriving high-probability and expected-regret guarantees.

A.1 Computational tractability and finite-precision implementation

  • Both arm-selection objectives admit QCQPs with nine quadratic constraints; the second requires the supremum in H_V to be attained within a known rational radius R.The QCQPs use two scalar variables in addition to the arm and dual vector.Source: §A.1 · pp. 21–22
  • In polynomial time, Lemma 18 either finds an arm with K̂_V(x) empty or certifies that every arm’s enlarged K̂_out_V,η set is nonempty.Its running time is polynomial in d_X, d_D, log(1/η), and the bit length of V.Source: §A.1 · pp. 23–24
  • When η√n ≤ 1/2 and every enlarged set is nonempty, a polynomial-time algorithm returns rational x with H_4V(x) ≥ max_x′ H_4V(x′) − κ.Enlarging the ellipsoid to 4V provides an interior margin, which bounds the norm of a maximizing dual vector and supports the QCQP approximation.Source: §A.1 · pp. 24–25
  • The approximate arm rule retains Theorem 15’s regret rate: scoring with 2E_V doubles the middle term, while choosing κ makes Tκ = 1.The analysis takes n = ⌈T^2/3⌉ and δ = (T + 1)^−2, as in Theorem 15.Source: §A.1 · pp. 25–26
  • With rational observations of polynomial bit length, the complete learner runs in time polynomial in |ϕ| and T.Each block calls the polynomial-time procedures of Lemmas 18 and 20 as needed, using rational arithmetic and stored matrices of polynomial bit length.Source: §A.1 · p. 26
  • The block proof holds an arm fixed within each block, uses block-length weights to cancel the 1/n_j noise factor, and sums at most J′max + 1 blocks covering T rounds.The blocks include the completed blocks and possibly a final block cut short by the horizon.Source: §A.1 · pp. 27–28
  • With δ = (T + 1)^−2, the failure-event contribution to expected regret is at most Cr/T.Outside the high-probability event, regret is at most CrT, so its expected contribution is at most CrTδ.Source: §A.1 · p. 28

B.1 Computational tractability and finite-precision implementation

Algorithm 2’s arm-selection step is formulated as a QCQP and solved approximately in polynomial time. The repair preserves the regret rate, yielding a polynomial-time learner with the stated regret guarantee.

B.1 Computational tractability and finite-precision implementation

  • The maximization of U_V,λ over arms is the optimal value of a QCQP with six quadratic constraints, whose optimal arm maximizes U_V,λ.The program has a nonempty feasible set and satisfies Theorem 9’s hypotheses.Source: §B.1 · p. 29
  • A polynomial-time algorithm returns a rational arm whose score is within κ of the maximum, with runtime polynomial in the dimensions, log λ, log(1/κ), and input bit lengths.The solver’s approximate point is repaired to satisfy the constraints while controlling objective loss.Source: §B.1 · p. 29
  • Rational observations of polynomial bit length keep the learner’s stored matrices and per-round computations polynomial-time.The matrices satisfy I_q ⪯ V ⪯ (1 + 3T)I_q, bounding their trace and supporting polynomial bit-length implementation.Source: §B.1 · p. 30
  • The learner runs in time polynomial in |ϕ| and T while retaining the regret bound of Theorem 1.The analysis sets κ = 1/T, so the approximate arm choice adds at most 1 to the high-probability regret bound.Source: §B.1 · p. 30

C NP-hardness results

The section shows that planning hardness can transfer to robust-bandit learning under stated sampling and regret conditions. It uses this reduction to explain why natural variations of the linear problem can become NP-hard.

C.1 Planning from learning

  • The planning-to-learning reduction turns NP-hard planning instances into NP-hard learning instances.The reduction uses a sampler for outcomes consistent with the known hypothesis and a learner with sublinear regret.Source: §C.1 · pp. 30–31
  • A polynomial-time learner with regret at most P(|ϕ|)T^(1−α), together with efficient near-minimizing outcome samplers, yields an approximately optimal arm in polynomial time.The returned arm has V_h − v_h( x̂ ) ≤ ε with probability at least 2/3.Source: §C.1 · pp. 30–31

C NP-hardness results

  • The authors identify smoothness of the arm and outcome sets as important for efficiency; convex shapes with edges and corners can enter NP-hard territory.The section’s hardness results concern natural variations of the linear robust-bandits problem.Source: C NP-hardness results · p. 30, §C.1 · p. 31

C.2 D = simplex, X = ball

For ball arms and simplex outcomes, the paper reduces MAX-CUT to robust-bandit planning and then transfers the hardness to learning. Under the stated regret guarantee, randomized learning would imply NP ⊆ BPP, while deterministic learning would imply P = NP.

C.2 D = simplex, X = ball

  • A randomized polynomial-time learner with regret at most P(|ϕ|)T^(1−α) for all parameters and true hypotheses implies NP ⊆ BPP; a deterministic learner implies P = NP.This result is for the setting with D a simplex instead of a ball.Source: §C.2 · p. 31
  • The construction links a sign vector’s graph-incidence norm to the size of its cut, then uses feasible arms and their minimizing outcomes to establish the reduction.The resulting equivalence connects a qualifying arm to a MAX-CUT yes-instance.Source: §C.2 · pp. 32–34
  • The reduction encodes MAX-CUT so that an approximate planning value distinguishes graphs with cut size at least k from those with cut size at most k − 1.The chosen scale separates consecutive integer cut sizes, allowing a polynomial-time learner and planning reduction to decide MAX-CUT.Source: §C.2 · p. 34

C.3 A Euclidean outcome ball and a polytope of arms

Theorem 31 shows that replacing the Euclidean arm ball with a polytope makes sublinear-regret learning computationally hard under the stated conditions. Its reduction encodes MAX-CUT in approximate planning values.

C.3 A Euclidean outcome ball and a polytope of arms

  • The hardness holds even when the hypothesis is known and the arm set is a cube with only 2n defining inequalities.The cube nevertheless has 2^n vertices.Source: §C.3 · p. 34
  • A randomized polynomial-time learner with the stated regret guarantee for polytope arms would imply NP ⊆ BPP; a deterministic learner would imply P = NP.The guarantee is RT ≤ P(|ϕ|)T^(1−α) for fixed α > 0 and polynomial P.Source: §C.3 · p. 34
  • The reduction makes approximating the constructed hypothesis value identify the graph’s maximum-cut size.The quadratic objective can be maximized at a sign vector, where its value encodes the cut size.Source: §C.3 · p. 35
  • The reduction recovers a maximum cut by rounding the learner’s arm to a sign vector without decreasing the encoded objective.A lower cut value would contradict the approximation gap between consecutive candidate values.Source: §C.3 · p. 36

C.4 Trilinear constraints with Euclidean arm and outcome balls

Allowing outcome-constraint coefficients to depend on the arm makes planning NP-hard even approximately. Under the stated regret guarantee, a randomized polynomial-time learner would imply NP ⊆ BPP, while a deterministic one would imply P = NP.

C.4 Trilinear constraints with Euclidean arm and outcome balls

  • The hardness arises when constraint coefficients for the outcome are allowed to depend on the arm, making the constraints trilinear.This remains within the broader robust-bandits framework described in the passage.Source: §C.4 · p. 36
  • A randomized polynomial-time learner for the trilinear setting with the stated regret bound would imply NP ⊆ BPP; a deterministic learner would imply P = NP.The setting retains Euclidean balls for arms and outcomes and a linear reward.Source: §C.4 · p. 37
  • In the reduction, each feasible-outcome set is a singleton independent of the hypothesis parameter, and the transversality inequality holds with a constant greater than 0.88.The constructed instance still yields NP-hard value approximation.Source: §C.4 · p. 38
  • The reduction encodes CLIQUE so that inverse-polynomial additive accuracy in the optimal value decides whether the graph contains a k-clique.An estimate within ε lies on opposite sides of a threshold depending on whether the clique number is at least k or at most k−1.Source: §C.4 · pp. 39–40

C.5 Efficient planning does not imply efficient learning

The paper gives instances where planning for a known hypothesis is easy but efficient learning would imply NP = RP. The reduction works by using observations compatible with every k-clique, forcing a learner to find one.

C.5 Efficient planning does not imply efficient learning

  • There are instances with O(n^2)-time planning for a known hypothesis where a randomized polynomial-time learner with the stated regret guarantee would imply NP = RP; deterministically it would imply P = NP.The family uses parameters ϕ = (n, k), with 2 ≤ k ≤ n given in unary.Source: §C.5 · p. 40
  • The reduction presents outcomes compatible with every k-clique, so a low-regret learner must find a clique rather than rely on hypothesis-specific planning.The arms and hypotheses correspond to k-element subsets, with the optimal arm matching the hypothesis’s subset.Source: §C.5 · p. 40
  • The reduction’s randomized search is an RP algorithm for CLIQUE, and it still works when regret is guaranteed only against the repeated outcome used in the construction.CLIQUE is NP-complete, yielding NP = RP; deterministic search gives P = NP.Source: §C.5 · p. 42
  • The example lies outside the paper’s Euclidean-ball and linear-reward setting, using exponentially large finite arm and hypothesis sets, a polytope outcome set, and a bilinear reward.The sets are represented by k-subsets.Source: §C.5 · p. 42

Related papers

Loading 2610.08740v1…