An Improved Algorithm for Adversarial Linear Contextual Bandits via Reduction

We thank the reviewer for their time and for providing an insightful review. Please see our responses below.

Q1: The details of the misspecification-robust adversarial linear bandit algorithm are deferred to the appendix, and little intuition regarding the proof of Theorem 2 is provided in the main text. This makes it difficult to assess the significance of the adversarial linear bandit algorithm, particularly for readers unfamiliar with the misspecification-robust setting.

A1: Thanks for the suggestion. We will add more explanation for Algorithm 2 in the revision. While its guarantee is new, its main algorithmic elements are from prior work. It is a simplified and improved version of Liu et al. (2024)’s Algorithm 3 (the simplification and the improvement in the bound are possible because in our case the amount of misspecification $\epsilon$ is the same in all rounds). Liu et al. (2024)’s algorithm, in turn, is a combination of the clipped continuous exponential weights of Ito et al. (2020) that guarantees optimal small-loss bound with polynomial computational complexity, and the bonus design in Zimmert and Lattimore (2022) that ensures misspecification robustness (though their original goal is high-probability bound).

Liu, Tajdini, Wagenmaker, Wei. Corruption-Robust Linear Bandits: Minimax Optimality and Gap-Dependent Misspecification. 2024.

Ito, Hirahara, Soma, Yoshida. Tight First- and Second-Order Regret Bounds for Adversarial Linear Bandits. 2020.

Zimmert and Lattimore. Return of the bias: Almost minimax optimal high probability bounds for adversarial linear bandits. 2022.

Q2: In equation (1), how to detail with possibly multiple minimizers?

A2: Our results allow ties to be broken arbitrarily. The regret analysis is agnostic to the tie-breaking rule used. We will clarify this in the revision.

Q3: In the equation after line 121, what is the rightmost expectation taken about?

A3: The rightmost expectation is taken over the randomness in $\pi_t$ (i.e., the random policy selected by the algorithm at time $t$).

Q4: I could not understand the rightmost expression of $\hat{\Omega}$ after line 125. Why does it contain neither $\pi$ nor $\Pi$?

A4: This can be seen by the following equalities. For simplicity, let’s first assume $\mathcal{A}_1, \ldots, \mathcal{A}_N$, which are drawn i.i.d. from $\mathcal{D}$, are all distinct.

$\hat{\Omega}$

$= \lbrace \hat{\Psi}(\pi) \mid \pi\in\Pi \rbrace$

$= \lbrace \mathbb{E}_{\mathcal{A}\sim \tilde{D}} [\pi(\mathcal{A})] \mid \pi\in\Pi \rbrace$       // by the definition of $\hat{\Psi}$, where $\tilde{D}$ is the empirical context distribution

$= \lbrace \frac{1}{N} \sum_{i=1}^N \pi(\mathcal{A}_i) \mid \pi\in\Pi \rbrace$

$= \lbrace \frac{1}{N} \sum_{i=1}^N a_i \mid a_i \in \text{conv}(\mathcal{A}_i) \rbrace$

The key is in the last inequality: Recall that $\pi$ is a mapping from an action set $\mathcal{A}$ to an element in conv($\mathcal{A}$), and $\Pi$ contains all such mappings. When $\mathcal{A}_1, \ldots, \mathcal{A}_N$ are all different, we can freely choose $\pi(\mathcal{A}_i)$ as an element $a_i \in \text{conv}(\mathcal{A}_i)$ for every $i$. This is essentially the last expression.

If there exist $i\neq j$ such that $\mathcal{A}_i=\mathcal{A}_j$, then we have the additional constraint that $a_i= \pi(\mathcal{A}_i) = \pi(\mathcal{A}_j)=a_j$.

Q5: In line 194, what is the specific amount of the misspecification $\epsilon$? Does it come from the uniform convergence bound?

A5: Yes, $\epsilon$ comes from the uniform convergence bound. Its value is essentially the right hand side of Line 132 with $b=1$ and $N=\Theta(t)$ (the number of contexts the learner has collected up to time $t$).

Thank you for pointing out the typo in the minor comment.

We thank the reviewer for their time and for providing an insightful review. Please see our responses below.

Q1: Maybe the authors can add more explanations to Algorithm 2 in the main text. Currently, it seems that the authors just list Algorithm 2 and its guarantee without introducing more about the intuition and the procedure.

A1: Thanks for the suggestion. We will add more explanation for Algorithm 2 in the revision. While its guarantee is new, its main algorithmic elements are from prior work. It is a simplified and improved version of Liu et al. (2024)’s Algorithm 3 (the simplification and the improvement in the bound are possible because in our case the amount of misspecification $\epsilon$ is the same in all rounds). Liu et al. (2024)’s algorithm, in turn, is a combination of the clipped continuous exponential weights of Ito et al. (2020) that guarantees optimal small-loss bound with polynomial computational complexity, and the bonus design in Zimmert and Lattimore (2022) that ensures misspecification robustness (though their original goal is high-probability bound).

Liu, Tajdini, Wagenmaker, Wei. Corruption-Robust Linear Bandits: Minimax Optimality and Gap-Dependent Misspecification. 2024.

Ito, Hirahara, Soma, Yoshida. Tight First- and Second-Order Regret Bounds for Adversarial Linear Bandits. 2020.

Zimmert and Lattimore. Return of the bias: Almost minimax optimal high probability bounds for adversarial linear bandits. 2022.

Q2: Based on my understanding, the reason why first-order regret bound is not obtained for the unknown context distribution setting is that the action set approximation error can not be related to the loss of the algorithm. I wonder whether there are some methods to address this?

A2: To make the action set approximation error related to the loss of the algorithm, we essentially need a counterpart of Bernstein inequality for our Lemma 1 (the concentration bound based on Rademacher complexity). There are some related tools in the literature, such as local Rademacher complexity (Bartlett et al., 2005) and offline Rademacher complexity (Liang et al., 2015). However, we haven’t found a way to integrate them into our framework and left it as a future work. We will provide more discussions on this in the revision.

Bartlett, Bousquet, Mendelson. Local Rademacher complexities. 2005.

Liang, Rakhlin, Sridharan. Learning with Square Loss: Localization through Offset Rademacher Complexity. 2015.

We thank the reviewer for their time and for providing an insightful review. Please see our responses below.

Q1: The optimal regret $d\sqrt{T}$ is currently achieved either inefficiently or with a polynomial number of calls to a simulator. The question whether the optimal regret could be achieved in poly time (even allowing a dependence on $K$) and without using a simulator seems rather fundamental and is not directly addressed by your work. Could your techniques provide any insight on this question?

A1: This is indeed a fundamental question. Unfortunately, our techniques don't directly resolve the gap between the regret with and without simulators.

The suboptimality in both our bound and Liu et al. (2023) stems from the same core issue: we approximate the true context distribution using empirical samples collected before time $t$, then evaluate the learner's policy on this empirical distribution. Since the empirical samples and the learner's policy are correlated, we must use a uniform convergence bound over all policies, which introduces the extra $d$ factor.

For the special case where action sets are subsets of the standard basis in $\mathbb{R}^K$ (i.e., sleeping bandits), Schneider and Zimmert (2023) developed a sophisticated algorithm to avoid this correlation and achieve the optimal $\sqrt{KT}$ bound. It is not yet clear how to generalize their approach to our setting. We will add this reference and discuss it in our revision.

Schneider and Zimmert. Optimal cross-learning for contextual bandits with unknown context distributions. 2023.

Q2: Is your algorithm the first one working in the convex hull of the action set? What did prevent previous approaches to depend on $C$ rather than $K$?

A2: Yes, our algorithm is the first to achieve computational complexity depending only on $C$ rather than $K$.

All previous works studying this problem are built on the approach of (Neu and Olkhovskaya, 2020), which runs an individual linear bandit algorithm on each possible action set, with the loss estimators shared between action sets. Except for Liu et al. (2023), all works use exponential weights over actions, whose computational complexity scales with $K$. Liu et al. (2023) uses FTRL with a log-determinant barrier (logdet-FTRL), whose computational complexity still scales polynomially with $K$.

We initially attempted to modify Liu et al. (2023)'s approach by substituting logdet-FTRL with a linear bandit algorithm whose computation does not scale with K (e.g., SCRiBLe and continuous exponential weights), but that failed: for technical reasons, these algorithms do not seem to allow using shared loss estimators among action sets.

In this paper, we adopt a different approach that runs linear bandit over a "single action set" constructed by averaging up the empirical contexts. This allows us to run SCRiBLe or continuous exponential weights on it without incurring the previous issue.

Q3: There is a large body of literature proposing algorithms that simultaneously achieve optimal (or near-optimal) stochastic and adversarial regret bounds for bandits (best of both worlds). Could your techniques be applied to obtain results in this direction?

A3: For adversarial contextual bandits with stochastic contexts, there is indeed work investigating best-of-both-worlds guarantees under the assumption of known context distribution or access to a simulator (Kato and Ito, 2023; Kuroki et al., 2024). In this case, our approach can also achieve best-of-both-worlds results by simply reducing our problem to a linear bandit algorithm with best-of-both-worlds guarantees.

However, when the context distribution is unknown and there is no simulator, our current technique faces a limitation: the misspecification parameter $\epsilon=\tilde{\Theta}(1/\sqrt{t})$ introduced in our reduction to linear bandits causes the regret to scale as $\sqrt{T}$ even in stochastic environments, preventing us from achieving the $\log(T)$ regret characteristic of the stochastic setting. Resolving this would be an interesting future direction.

Kato, Ito. Best-of-Both-Worlds Linear Contextual Bandits. 2023.

Kuroki, Rumi, Tsuchiya, Vitale, Cesa-Bianchi. Best-of-Both-Worlds Algorithms for Linear Contextual Bandits. 2024.

We thank the reviewer for their time and for providing an insightful review. Please see our responses below.

Q1: In the definition of linear bandits, does the learner incur the loss they see as feedback or do they incur $\langle y_t, \theta_t\rangle$?

A1: Our Eq.(2) assumes the learner incurs the loss $\langle y_t, \theta_t\rangle$. However, if instead the learner incurs the observed loss, the regret bounds differ by at most $2\epsilon T$ under our misspecification assumption—a difference that can be absorbed by the last term in Eq.(2). Thus, both interpretations work.

Q2: The definition of regret in line 84 seems wrong; there should be an expectation over $\mathcal{A}_t$?

A2: Thank you for pointing this out. You are right—the regret definition in line 84 should include an expectation over $\mathcal{A}_t$. We will correct this in the revision. Note that our theoretical analysis indeed takes expectation over $\mathcal{A}_t$.

Q3: Line 90: "learner decides": I think you mean adversary decides?

A3: Thank you for catching this. Yes, it should be "adversary decides".

Q4: The reduction seems fairly generic. Are there similar problems in which the authors believe such approaches would work? Alternatively, are there similar examples known in the literature the authors are aware of?

A4: Yes, our reduction approach has broader applicability. We will discuss two relevant examples:

First, our problem setting is a special case of MDPs with fixed transitions and adversarial losses, which has been extensively studied recently. Our approach provides a potential solution for such settings when dealing with continuous or exponentially large action spaces.

Second, recent work on linear Markov games (Wang et al. 2023; Dai et al. 2024) reduces the problem to adversarial linear contextual bandits with stochastic action sets. While their regret guarantees are independent of the number of actions $K$, their computational complexity still scales with $K$. Our approach could potentially eliminate this computational dependence on $K$ in their setting as well.

Wang, Liu, Bai, Jin. Breaking the curse of multiagency: Provably efficient decentralized multi-agent rl with function approximation. 2023.

Dai, Cui, Du. Refined Sample Complexity for Markov Games with Independent Linear Function Approximation. 2024.

Q5: It would be good if you provide a more detailed comparison of your reduction with that of Hanna et al.

A5: Thanks for the suggestion. We will add an extensive comparison with Hanna et al. in our final version. While the reductions are conceptually related, the key difference lies in our primary focus on computational efficiency. Their work only focuses on regret bounds, and there are still gaps in making their algorithm polynomial time.

Specifically, we reduce the problem to linear bandits with domain $\hat{\Omega}$ — the image under $\Psi$ of all policies $\pi$ — which is a polytope with poly($d$, $C$, $T$) linear constraints that allows for linear programming tools. On the other hand, Hanna et al. reduce the problem to linear bandits with domain $\mathcal{X}$ — the image under $\Psi$ of linear policies $\pi_\phi$ where $\phi$ comes from an $\epsilon$-net of $\mathbb{R}^d$ — which has $T^d$ discretized points. It remains unclear how their algorithm efficiently: 1) constructs and maintains these points and 2) runs a linear bandit over them. While they mention Phased Elimination, this algorithm has computational complexity scaling with the number of actions ($T^d$ in their case).

Dealing with the polytope requires novel techniques, including our method of mapping a point in $\hat{\Omega}$ to policies (Section 3.2), and our analysis that bounds the estimation error using Rademacher complexity (Section 3.3) rather than discretization plus Hoeffding’s inequality and a union bound as in Hanna et al.

Finally, we operate on the adversarial setting while they on the stochastic setting, a strict generalization.