← Back to all news
arXiv Machine Learning By Yinan Li, Kwang-Sung Jun, Kapilan Balagopalan, Tuan Nguyen, Yao Zhao, Abbas Zaidi, Houssam Nassif

Halve-Then-Greedy: Adaptive Sampling for Posterior Success with Near-Optimal Instance Dependence

Read the original on arXiv Machine Learning →

The paper introduces Halve-Then-Greedy (HTG), an adaptive sampling strategy for fixed-budget experimentation that maximizes the probability of obtaining sufficient posterior evidence that a recommended design’s mean performance exceeds a target. HTG combines an initial balanced allocation, successive halving, and posterior-greedy sampling, and the authors prove instance-dependent, finite-budget exponential bounds on posterior-failure probability. They also establish that HTG matches an asymptotic sample-complexity lower bound up to a logarithmic factor and demonstrate, through analysis and simulations, that HTG outperforms uniform sampling and sequential halving in terms of sample efficiency.

Machine-generated by The Flow from the publisher's headline and feed description — not written or checked by a human. The full article lives at arXiv Machine Learning.

Related stories

Hugging Face Trending Papers
Jun 8

Asymptotic Optimality of Thompson Sampling for Risk-Averse Bandits with Sub-Gaussian Rewards

We prove that $ρ\text{-}\mathrm{NPTS}_{\mathrm{SG}}$, an anchor-free nonparametric Thompson Sampling algorithm for risk-averse bandits, achieves regret matching the instance-dependent lower bound to leading order in $\log n$, establishing it as asymptotically optimal for any continuous risk functional $ρ$ (CVaR, mean-variance, Sharpe ratio, distortion risk measures, and more) on the class of distributions with bounded density and sub-Gaussian tails, including Gaussian arms. Both this result and its bounded-support counterpart require only continuity of $ρ$: strictly weaker than the dominance condition of prior parametric Thompson Sampling results, and strictly weaker than the Lipschitz condition of UCB-type algorithms, yielding the first instance-optimal guarantees for non-Lipschitz functionals such as the Sharpe ratio without parametric reward assumptions.

More like this →
arXiv Machine Learning
Sep 25

Exact Bayes Regret and Asymptotic Optimality in High-Dimensional Gaussian Bandits

The paper analyzes Bayesian linear bandits with isotropic Gaussian parameters, independent Gaussian arms, and Gaussian reward noise when the time horizon scales with the dimension. It derives explicit limits for the normalized posterior uncertainty and parameter overlaps, yielding exact regret curves for several policies—including Thompson sampling, posterior‑mean greedy selection, and scaled‑covariance variants. The results show that posterior‑mean greedy selection achieves the optimal Bayes regret, while Thompson sampling incurs a strictly larger leading regret whose ratio to greedy lies between one and two, approaching two for long horizons.

By Prakhar Singhvi (Abstract Math Institute), Yi Zou (Abstract Math Institute), Abhishek Bhattacharjee (Abstract Math Institute)
reinforcement-learning
More like this →