Setting $m=1$ proves that the $\log K$ for ordinary $K$-armed bandits against adaptive non-anticipating adversaries is unavoidable, closing the remaining $\sqrt{\log K}$ gap between confidence-tuned upper and lower bounds left by Gerchinovitz and Lattimore.
Abstract
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 complement this upper bound with a matching high-probability lower bound. For all sufficiently small $\delta$, every randomized policy admits a deterministic adaptive non-anticipating adversary for which, with probability at least $\delta$, \[ R_T = \Omega\left(\sqrt{dT\log(K/\delta)}\right). \] Thus, the rate is minimax optimal up to universal constants in this regime. In particular, setting $m=1$ proves that the $\log K$ for ordinary $K$-armed bandits against adaptive non-anticipating adversaries is unavoidable, closing the remaining $\sqrt{\log K}$ gap between confidence-tuned upper and lower bounds left by Gerchinovitz and Lattimore.
An algorithm is designed that achieves second-order path-length regret in adversarial $K$-armed bandits against oblivious loss sequences 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
An expected approximation guarantee of an expected approximation guarantee of $8(\ln k+2)\left(\frac{1+\varepsilon}{1-\varepsilon}{1-\varepsilon}\right)^4 = (1+O(\varepsilon))\,8(\ln k+2)$.
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.