We study adversarial combinatorial bandits with $m$-set actions, where at each round the learner selects $m$ out of $d$ items and observes only the aggregate loss of the selected items. The resulting action set contains $K=\binom{d}{m}$ elements and can therefore be exponentially large. Nevertheless, the loss of every action is determined by the same $d$-dimensional vector of item losses. We propose a computationally efficient algorithm that exploits this structure without explicitly enumerating the action set. Against adaptive non-anticipating adversaries, it guarantees, with probability at least $1-\delta$, regret against the best fixed action of \[ R_T = O\left(\sqrt{dT\log(K/\delta)}\right). \] This matches the high-probability regret bound of the finite-action EXP3-KW algorithm of Zimmert and Lattimore, whose direct implementation may require exponential space. Our algorithm instead represents each sampling distribution with $d$ parameters and runs in polynomial time without enumerating the action set. Thus, it resolves the open problem posed by Maiti et al.
We study second-order path-length regret in adversarial $K$-armed bandits against oblivious loss sequences. Bubeck et al. [2019] designed an algorithm that achieves $\widetilde{\mathcal{O}}(K+\sqrt{KQ_{\infty,1}})$ regret, where $Q_{\infty,1}$ is the first-order path length, and left open whether $\widetilde{\mathcal{O}}(\text{poly}(K)\sqrt{1+Q_{\infty,2}})$ regret is achievable under bandit feedback, where $Q_{\infty,2}$ is the second-order path length. Somewhat surprisingly, we resolve this question positively by showing that with a more involved analysis, the exact same algorithm of Bubeck et al. [2019] achieves $\mathcal{O}\left(K\log(KT)+\sqrt{K\log(KT)\bigl(1+Q_{\infty,2}\bigr)}\right)$ expected regret when $Q_{\infty,2}$ is known, where $T$ is the horizon. This matches the $\Omega(\sqrt{KQ_{\infty,2}})$ lower bound up to logarithmic factors and additive terms. We further remove the knowledge of $Q_{\infty,2}$ using an adaptive restart scheme whose path-length estimator has uniformly bounded increments.
Let $p_0,p_1,\ldots,p_N$ be points of the unit ball of $\mathbb R^d$, processed in a prescribed order. We study the insertion cost $\sum_{i=1}^N\lVert p_i-x_{i-1}\rVert^\alpha$, where each $x_{i-1}$ is computed from the previously observed points. The input-order path is sensitive to the input distribution but can repeatedly pay the diameter under adversarial input. The center star has controlled worst-case scale but ignores the observed sequence. We compress the past into one point through $x_0=p_0$ and $x_i=\gamma x_{i-1}+(1-\gamma)p_i$, where $0\leq\gamma\leq1$. Thus $x_i$ is an exponentially weighted memory of the input, maintained with one $d$-dimensional point of working state. For independent uniform points, the stationary insertion length is nonincreasing in the usual stochastic order as $\gamma$ increases. If $d\geq2$ and $\alpha>0$, every optimal constant parameter for $N$ insertions satisfies $1-\gamma_N^*=\Theta(N^{-1/2})$. We determine its asymptotic constant and the resulting $\sqrt N$ correction, with explicit bounds in $d$ and $\alpha$. For $\alpha=1$, the leading expected tree length equals that of the center star and is strictly smaller than those of the endpoint constructions. For $\alpha=2$, the minimizer is unique for $N\geq2$, with $1-\gamma_N^*=N^{-1/2}-\tfrac12N^{-1}+O(N^{-3/2})$. For arbitrary input sequences and fixed $0\leq\gamma<1$, the largest asymptotic mean cost is $(2/(1+\gamma))^\alpha$ for $0<\alpha\leq3$, strictly below the path value when $\gamma>0$. Among fixed nonnegative weighting rules whose contributing points have the same average distance in the input order from the most recent point, exponential weighting is within a factor smaller than $1.161^\alpha$ of the best adversarial value in dimension at least two; this ratio tends to one as that average distance grows.
We study the bandit-feedback version of online principal component analysis (Bandit PCA): in each round $t = 1,\dots,T$, the adversary selects a $d \times d$ symmetric gain matrix $G_t$ with spectrum in $[0,1]$ and rank at most $r$; the learner simultaneously selects a unit vector $w_t \in S^{d-1}$ and receives the reward $w_t^\top G_t w_t$. The learner receives no other feedback, and aims to minimize the regret against the best unit vector in hindsight. This problem was introduced by Kotlowski and Neu (2019), who gave an algorithm with regret $O(d\sqrt{rT \log T})$ and showed the lower bound of $\Omega(r\sqrt{T/\log T})$. We improve upon both of these bounds and essentially bridge the gap between them, establishing the minimax regret of order $r\sqrt{dT}$ up to polylogarithmic factors in $d$ and $T$. The upper bound is attained by a novel algorithm, which combines online mirror descent on the spectrahedron of (real) density matrices with a multiscale exploration scheme in which the eigenspaces with different spectral magnitudes are updated at different rates. For the lower bound, we construct an adaptive adversary that refines a hidden large-reward subspace based on the learner's actions, in such a way that low regret is impossible without estimating the subspace; as a result, lower-bounding the regret reduces to studying the arising subspace estimation problem. Finally, we discuss connections of Bandit PCA with adaptive-measurement quantum tomography.
Moise Blanchard, Dmitrii M. Ostrovskii, Aadirupa Saha· 0 citations
The celebrated $k$-means++ algorithm of Arthur and Vassilvitskii (SODA 2007) achieves an $O(\log k)$ expected approximation for the classical $k$-means problem using $D^2$-sampling, a technique now ubiquitous in clustering algorithm design. Bhattacharya et al. (ESA 2020) introduced $\varepsilon$-noisy $k$-means++, where sampling probabilities may incur an adversarial multiplicative error of $(1\pm\varepsilon)$, but obtained only an $O(\log^2 k)$ guarantee. Grunau et al. (ESA 2023) recovered the asymptotic $O(\log k)$ guarantee, but their analysis loses a constant factor of roughly $147{,}638$ even as $\varepsilon\to0$, leaving open whether $k$-means++ is highly sensitive to even a small amount of noise. They asked whether a bound within $1+O(\varepsilon)$ of the classical guarantee is possible. We resolve this affirmatively, proving an expected approximation guarantee of $8(\ln k+2)\left(\frac{1+\varepsilon}{1-\varepsilon}\right)^4 = (1+O(\varepsilon))\,8(\ln k+2)$. We complement the upper bound with two separations. First, a noisy version of the Arthur and Vassilvitskii lower-bound instance incurs a $1+\Omega(\varepsilon)$ loss over exact $k$-means++, so linear dependence on the noise is necessary. Second, pointwise multiplicative control is qualitatively essential: replacing it with per-round total variation closeness admits no finite approximation guarantee, even for $k=2$.
We study structural recovery from an exact but adversarially corrupted set observation over $\mathbb F_2^n$. A hidden nonempty set $A$ satisfies $|A+A|\leq K|A|$, while the algorithm receives deterministic membership access and independent exact uniform samples only from a set $B$ satisfying $|A\triangle B|\leq\eta|A|$. For $\eta\leq cK^{-1/2}$, we give a randomized FPT-form algorithm which, with high probability, outputs a subspace $V$ satisfying $|V|\leq|A|$ and $\mathcal N_V(A)\leq K^{O(1)}$. For every supplied $\eta<1$, writing $\varepsilon=1-\eta$, we also give an observation-only algorithm that outputs $O(\sqrt K\,\varepsilon^{-2}\log(3/\varepsilon))$ subspaces. For every hidden set compatible with $B,K,\eta$, some list entry has size at most that hidden set and covering number $\operatorname{poly}(K,\varepsilon^{-1})$. The sample complexity is polynomial, while the direct query and running-time bounds are XP. Every nonempty compatibility class also admits, nonconstructively, one common subspace $V$ such that $|V|\leq|A|$ and $\mathcal N_V(A)\leq2K(1-\eta)^{-1}P_{\rm PFR}(K)$ simultaneously for every compatible hidden set $A$. An exact two-subspace construction forces common covering cost $\Theta((1-\eta)^{-1/2})$, leaving quantitative and algorithmic list-to-single gaps. We further show that the $K^{-1/2}$ contamination scale is optimal up to constants for the one-core, size-only lifting mechanism used in the single-output argument. The proofs combine a persistent randomized Balog-Szemer\'edi-Gowers procedure producing a fixed implicit small-doubling subset on the $\sqrt{\alpha}$ retained-mass scale, conditionally exact finite product sampling, size-oblivious algorithmic PFR, and deterministic lifting.
We study the expected improvement (EI) policy for minimizing a deterministic objective function $f$ on a nonempty compact set $\mathcal X \subset\mathbb R^d$. We assume that $f$ belongs to the RKHS $\mathcal H_k$ of a continuous positive-semidefinite kernel $k$ on $\mathcal X$. Function values are observed exactly, and EI is computed from a fixed zero-mean Gaussian-process model with covariance $\sigma^2k$. After an initial design, the policy queries a point whose EI is at least a fixed positive fraction of its maximum. We identify the normalized posterior standard deviation at a candidate point $x$ with the norm of the corresponding innovation in the canonical feature space, namely the component of $k(x,\cdot)$ orthogonal to the span of the preceding evaluation representers. Sequential separation radii bound the ranked innovation norms along arbitrary query sequences. We estimate these radii using Gram determinants and Kolmogorov widths for subspaces of different dimensions, then combine the estimates with a one-step regret inequality to obtain finite-budget bounds for simple regret. After $N$ post-initial queries, simple regret is $O(N^{-\nu/d})$ for isotropic Mat\'ern kernels of smoothness $\nu>0$. For the isotropic squared-exponential kernel, simple regret is $O(\exp[-c_1\min\{N, N^{1/d}\log(eN)\}])$ for some $c_1>0$. With exact EI maximization, it is $O(\exp[-c_2N^{1/d} \log(eN)])$ for some $c_2>0$. For every fixed $B\geq0$, these bounds are uniform over the RKHS ball of radius $B$. If $\mathcal X$ has nonempty interior and $B>0$, then, among deterministic methods whose final recommendation may be any point of $\mathcal X$, the exact EI policy is minimax-rate optimal over the RKHS ball of radius $B$ for Mat\'ern kernels and minimax-rate optimal up to constants in the exponent for squared-exponential kernels.