CS Paper Radar

Gap Entropy and Almost Instance-Wise Optimal Best-Arm Identification

Jiarui Yao, Jiaxi Zhao, Xiangxin Zhou

cs.CC cs.AIcs.LG ·submitted 2026-09-12 04:31 UTC · v1
theory

Abstract

In the best-arm identification problem, we are given $n$ stochastic arms with unknown means and wish to identify the arm with the largest mean with probability at least $1-δ$, using as few samples as possible. We consider independent Gaussian rewards with unit variance and means in $[0,1]$. Chen and Li [2016] conjectured that the instance-wise sample complexity of this problem is characterized by the gap entropy, up to an additive term arising from the two-arm problem. In this paper, we resolve their gap-entropy and almost instance-wise optimality conjectures. For an instance $I$, let $Δ_{[i]}$ be the gap between the largest and the $i$-th largest mean, let $H(I)=\sum_{i=2}^{n}Δ_{[i]}^{-2}$, and let Ent$(I)$ denote the entropy of the normalized complexities of its dyadic gap groups. For every $0<δ<0.1$, we show that the order-oblivious instance-wise lower bound is $ Θ (H(I)[\log(1/δ)+Ent(I)]). $ We also give a single $δ$-correct algorithm with expected sample complexity $ O ( H(I)[\log(1/δ)+Ent(I)] +D\log(e+\log(e+D))),D=Δ_{[2]}^{-2}, $ without prior knowledge of the gaps. Our lower bound removes the dyadic-gap and monotonicity restrictions of previous work, and our upper bound removes the additional polylogarithmic factor multiplying the two-arm term. Thus, a single algorithm attains the instance-wise lower bound up to an additive two-arm term. The main theorems have been formalized and proved in Lean 4.

Closest papers

Nearest neighbours by meaning across the whole index.

A positive resolution of the gap-entropy conjecture

cs.LG stat.ML ·2026-09-09 ·P. M. Aronow, Nathan Kallus, Patrick Lopatto
theory similarity 0.83
Abstract

We prove the gap-entropy conjecture for fixed-confidence best-arm identification with independent unit-variance Gaussian arms, means in $[0,1]$, and a unique optimal arm. For each suboptimal arm $i$, let $Δ_i=μ_*-μ_i$ be its gap from the optimal mean, and write $H=\sum_{i\ne *}Δ_i^{-2}$. Let $p_r$ be the fraction of $H$ contributed by arms with $2^{-(r+1)}<Δ_i\le2^{-r}$, and let $\mathrm{Ent}(I)=\sum_{r:p_r>0} p_r\log(1/p_r)$. Among all algorithms that identify the optimal arm with probability at least $1-δ$ on every Gaussian instance, the optimal expected number of samples on a given instance, averaged over all permutations of the arm labels, is within absolute constant factors of $H(\log(1/δ)+\mathrm{Ent}(I))$. Moreover, there is an algorithm, independent of the instance, whose expected number of samples is bounded by a constant multiple of this quantity plus $g^{-2}\log\log(e^e/g)$, where $g=\min_{i\ne *}Δ_i$ is the gap to the closest competitor.

0.51

Best Arm Identification for Bandits with Shifting Means

cs.LG stat.ML ·2026-10-07 ·Lukas Zierahn, Wouter M. Koolen, Shubhada Agrawal, Christina Katsimerou, Dirk van der Hoeven
top venuetheoryhot direction similarity 0.64
Abstract · Accepted at NeurIPS 2026

We study the best arm identification problem in a stochastic environment with a novel form of adversarial perturbations, which we coin Shifting Means. While classically the mean rewards of the $K$ arms are stable in time, in Shifting Means only the gaps $\boldsymbolΔ$ between mean rewards are stable, while their common shift may be determined adversarially in each round. The objective of the learner is to identify the best arm with high probability while minimizing sample complexity (the fixed confidence setting). Handling shifts requires new tools: we show that algorithms employing a Generalized Likelihood Ratio Test (GLRT) stopping rule, including the popular Track-and-Stop, fail under time-varying shifts. Instead, we propose Importance Weights for Shifting Means ($\mathsf{ISM}$). Assuming means bounded by $U$ and $σ^2$-sub-Gaussian rewards, we show $\mathsf{ISM}$ to be $δ$-correct and to enjoy a sample complexity bound of order $K (σ^2 + U^2) Δ_{\min}^{-2} \ln \frac{1}δ$. We also present a matching (up to constant factors) worst-case lower bound and evaluate our results empirically.

0.45

An information identity reveals the geometry of deviation events

cs.IT ·2026-09-29 ·Akshay Balsubramani
similarity 0.63
Abstract

In a deviation event, the empirical measure of $n$ independent draws lands in a set of distributions. The exponent of its probability splits, at every $n$, into two nonnegative terms. The first is the rate: $n$ times the relative entropy, from the population, of the distribution of a typical draw under the event. The second is the dependence that conditioning induces among the draws, measured by their total correlation. Their relative sizes depend on the geometry of the set. This paper focuses on this exact split and on the geometry that the interplay of its two terms reveals. The dependence vanishes exactly when the event confines every draw to a single set, and the classical rate of that constraint is exact. On a set invariant under a compact group that fixes the population and leaves no invariant set of intermediate probability, the rate vanishes; uniform convergence over a hypothesis class that such a group permutes is one. On a half-space whose threshold sits a fixed number of standard errors above the mean, the fraction of the exponent that is dependence tends to a function of the event's probability alone. On a set split into pieces, the dependence is the pieces' average plus $n$ times the Jensen-Shannon divergence of their marginals, minus the entropy of their weights. The split extends to a general reference law. When the information projection is such a law, the split gives the exact value of the expectation in the exponential change of measure to the projection.

0.22

Tight Analysis of Randomized Truthful Scheduling: An $(m+1)/2$ Lower Bound

cs.GT ·2026-11-03 ·Wenqian Wang, Chenyang Xu, Yuhao Zhang
theory similarity 0.62
Abstract · 42 pages, 2 figures

The Nisan-Ronen conjecture, a central problem in algorithmic game theory, asserts that no deterministic truthful mechanism for makespan minimization on $m$ unrelated machines can achieve an approximation ratio better than $m$. Christodoulou, Koutsoupias, and Kovács resolved it in 2023, but the optimal approximation ratio achievable by randomized truthful mechanisms remained open. Recently, Anastasiadis, Christodoulou, Koutsoupias, Kovács, and Schecker extended techniques from the deterministic proof to establish a $(3/2-\sqrt{2})(m-1)$ lower bound for universally truthful mechanisms with discrete support and gave a universally truthful mechanism with approximation ratio $m/2+o(m)$. For the broader class of truthful-in-expectation (TIE) mechanisms, however, the gap remained large: the best known upper bound was $(m+5)/2$, while the lower bound was only $2-1/m$. We prove a lower bound of $(m+1)/2$, determining the optimal TIE approximation ratio up to an additive constant as $m/2+Θ(1)$. Our result also improves the leading constant in the lower bound for universally truthful mechanisms from $3/2-\sqrt{2} \approx 0.0858$ to $1/2$. Together with their $m/2+o(m)$ upper bound, our result determines the optimal approximation ratio for universally truthful mechanisms up to lower-order terms.

0.20

Near-Minimax Sample Complexity for Multi-Objective Reinforcement Learning under Generative Models

cs.LG stat.ML ·2026-11-03 ·Yue Wang
theory similarity 0.61
Abstract · Preprint, work in progress

In multi-objective reinforcement learning, preferences may be specified only after data collection, requiring one dataset to support a continuum of reward trade-offs. We study finite discounted Markov decision processes with unknown transitions, $S$ states, $A$ actions, and $m$ known reward functions taking values in $[0,1]$, given access to a generative model. The learner must provide an $\varepsilon$-optimal policy for every convex combination of these rewards without further sampling, with a guarantee that holds simultaneously over all preferences and initial states. Writing $H=(1-γ)^{-1}$, we establish the constant-confidence minimax sample complexity $\widetildeΘ\!\left( \frac{SAH^3}{\varepsilon^2}\min\{S,\log(em)\} \right)$, where the suppressed factors are logarithmic in $S,A,H,\varepsilon^{-1}$ and the dependence on $m$ is explicit. Thus, up to these logarithmic factors, the worst-case statistical cost of supporting all preferences grows logarithmically with the number of objectives and saturates at the number of states. The upper bound uses uniform state--action sampling and empirical planning, with reward rounding in the logarithmic-objective regime. Its analysis chains optimal-value increments over covers of the reward hull. A one-sided Bellman variance bound controls signed value differences under a second transition kernel, preserving the $H^3\varepsilon^{-2}$ dependence. A complementary uniform guarantee for all bounded rewards yields the state-dimension saturation. We establish lower bounds matching up to logarithmic factors through a rare-exit construction with subset rewards and action encoding. These bounds apply to adaptive simulator queries and arbitrary randomized history-dependent output policies, while the upper bounds are attained by deterministic stationary policies.

0.10

Sharp High-Entropy Bounds for Sums of Independent Discrete Random Variables

cs.IT ·2026-09-18 ·Haoran Wang
theory similarity 0.61
Abstract

Sharp high-entropy lower bounds for the entropy of a sum were known for identically distributed summands in torsion-free abelian groups and in prime cyclic groups. For arbitrary independent summands, Gavalakis, Goh and Kontoyiannis obtained an additive constant of $1/8$ and conjectured that the sharp constant is $1/2$. We prove that independent discrete random variables $X,Y$ with finite Shannon entropies satisfy $H(X+Y)\ge (H(X)+H(Y))/2+1/2-o(1)$ in every torsion-free abelian group as $\max{H(X),H(Y)}\to\infty$. The same conclusion holds in the prime cyclic group $\mathbb F_p$ when both $\max{H(X),H(Y)}$ and $\log_2 p-\max{H(X),H(Y)}$ tend to infinity. We give explicit error bounds in both settings. The proof extracts a component with paired point probabilities while controlling the entropy of the remainder independently of its support. Discrete rearrangement and uniform perturbation then transfer the continuous entropy power inequality to this component. In prime cyclic groups, an additional estimate controls the entropy lost under modular reduction. Binomial distributions show that the constant $1/2$ is optimal.

0.14

Sample-Optimal Multi-Group Learning with an ERM Oracle

cs.LG cs.DScs.GT ·2026-10-11 ·Princewill Okoroafor
theory similarity 0.60
Abstract

In multi-group learning, a single predictor must perform nearly as well as the best hypothesis in a class on every group in a rich, possibly infinite and overlapping, collection of subpopulations. The known algorithms with the optimal sample complexity keep track of every pair of a group and a hypothesis, which is impossible for the large classes of interest, and the known oracle-based algorithms have a worse rate. We ask whether the optimal rate can be attained by a learner that accesses the classes only through an empirical risk minimization (ERM) oracle. We give an algorithm that uses $\tilde{O}((d_G+d_H)/\varepsilon^2)$ samples and polynomially many calls to a weighted ERM oracle over pairs of a group and a hypothesis, where $d_G$ and $d_H$ are the VC dimensions of the group and hypothesis classes and $\varepsilon$ bounds the excess risk on every group, weighted by its probability. We also show a matching lower bound of $Ω((d_G+d_H)/\varepsilon^2)$ samples for every learner even with unlimited computation, so oracle efficiency costs no additional samples. We also consider a natural special case in which every input belongs to at most $k$ groups and these groups can be listed. In this case, an ERM oracle for the hypothesis class alone suffices, with $\tilde{O}((d_H+\log k)/\varepsilon^2)$ samples in the agnostic setting and $\tilde{O}((d_H+\log k)/\varepsilon)$ samples when every group has a hypothesis that is correct on it.

0.16

Settling the Sample Complexity of Rényi Entropy Estimation

cs.IT cs.DSmath.ST ·2026-10-07 ·Qisheng Wang
theory similarity 0.60
Abstract · 23 pages, 1 table

Rényi entropy estimation has been comprehensively investigated by Acharya, Orlitsky, Suresh and Tyagi (SODA 2015; IEEE Trans. Inf. Theory 2017) and consequent works, whereas only the sample complexity of Rényi entropy estimation of integer order has been settled. In this paper, we settle the sample complexity of Rényi entropy estimation of noninteger order, thereby completing the complexity picture of Rényi entropy estimation. Specifically, we show that for any noninteger $α> 0$, it is sufficient and necessary to use \[ Θ\!\left(\frac{d^{\max\{1/α,1\}}}{\varepsilon^{1/α}\log(d)} + \frac{d^{|1-1/α|}}{\varepsilon^2}\right) \] samples to estimate the Rényi entropy of order $α$ of an unknown discrete distribution over an alphabet of size $d$ to within additive error $\varepsilon$. For the upper bound, we reduce the bias using a refined polynomial approximation estimator for large probabilities. For the lower bound, we employ a different hard instance equipped with a new moment matching construction. The constructive moment matching has constant bounded high-order moments, while attaining a fixed ratio between the $α$-th moments, which is of independent interest.

0.20