Optimal Non-Asymptotic Lower Bound on the Minimax Regret of Learning with Expert Advice
We prove non-asymptotic lower bounds on the expectation of the maximum of $d$ independent Gaussian variables and the expectation of the maximum of $d$ independent symmetric random walks. Both lower bounds recover the optimal leading constant in the limit. A simple application of the lower bound for random walks is an (asymptotically optimal) non-asymptotic lower bound on the minimax regret of online learning with expert advice.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Asymptotically Optimal Fixed-Budget Best Arm Identification with Variance-Dependent Bounds
We investigate the problem of fixed-budget best arm identification (BAI) for minimizing expected simple regret. In an adaptive experiment, a decision maker draws one of multiple treatment arms based on past observations …
Minimax Optimal Simple Regret in Two-Armed Best-Arm Identification
This study investigates an asymptotically minimax optimal algorithm in the two-armed fixed-budget best-arm identification (BAI) problem. Given two treatment arms, the objective is to identify the arm with the highest exp…
Optimal Batched Linear Bandits
We introduce the E$^4$ algorithm for the batched linear bandit problem, incorporating an Explore-Estimate-Eliminate-Exploit framework. With a proper choice of exploration rate, we prove E$^4$ achieves the finite-time min…
Computational EfficiencyMulti-Armed BanditsA minimax and asymptotically optimal algorithm for stochastic bandits
We propose the kl-UCB ++ algorithm for regret minimization in stochastic bandit models with exponential families of distributions. We prove that it is simultaneously asymptotically optimal (in the sense of Lai and Robbin…
Data-driven optimal stopping: A pure exploration analysis
The standard theory of optimal stopping is based on the idealised assumption that the underlying process is essentially known. In this paper, we drop this restriction and study data-driven optimal stopping for a general …
Binary Classification