Tao Chao

Pinyan Lu, Chao Tao, Xiaojin Zhang

We study the problem of identifying the best arm in a stochastic multi-armed bandit game. Given a set of $n$ arms indexed from $1$ to $n$, each arm $i$ is associated with an unknown reward distribution supported on $[0,1]$ with mean $θ_i$ and variance $σ_i^2$. Assume $θ_1 > θ_2 \geq \cdots \geqθ_n$. We propose an adaptive algorithm which explores the gaps and variances of the rewards of the arms and makes future decisions based on the gathered information using a novel approach called \textit{grouped median elimination}. The proposed algorithm guarantees to output the best arm with probability $(1-δ)$ and uses at most $O \left(\sum_{i = 1}^n \left(\frac{σ_i^2}{Δ_i^2} + \frac{1}{Δ_i}\right)(\ln δ^{-1} + \ln \ln Δ_i^{-1})\right)$ samples, where $Δ_i$ ($i \geq 2$) denotes the reward gap between arm $i$ and the best arm and we define $Δ_1 = Δ_2$. This achieves a significant advantage over the variance-independent algorithms in some favorable scenarios and is the first result that removes the extra $\ln n$ factor on the best arm compared with the state-of-the-art. We further show that $Ω\left( \sum_{i = 1}^n \left( \frac{σ_i^2}{Δ_i^2} + \frac{1}{Δ_i} \right) \ln δ^{-1} \right)$ samples are necessary for an algorithm to achieve the same goal, thereby illustrating that our algorithm is optimal up to doubly logarithmic terms.

Guangyu Xi, Chao Tao, Yuan Zhou

We study MNL bandits, which is a variant of the traditional multi-armed bandit problem, under risk criteria. Unlike the ordinary expected revenue, risk criteria are more general goals widely used in industries and bussiness. We design algorithms for a broad class of risk criteria, including but not limited to the well-known conditional value-at-risk, Sharpe ratio and entropy risk, and prove that they suffer a near-optimal regret. As a complement, we also conduct experiments with both synthetic and real data to show the empirical performance of our proposed algorithms.

Chao Tao, Saùl Blanco, Jian Peng et al.

We consider the thresholding bandit problem, whose goal is to find arms of mean rewards above a given threshold $θ$, with a fixed budget of $T$ trials. We introduce LSA, a new, simple and anytime algorithm that aims to minimize the aggregate regret (or the expected number of mis-classified arms). We prove that our algorithm is instance-wise asymptotically optimal. We also provide comprehensive empirical results to demonstrate the algorithm's superior performance over existing algorithms under a variety of different scenarios.

Chao Tao, Qin Zhang, Yuan Zhou

Best arm identification (or, pure exploration) in multi-armed bandits is a fundamental problem in machine learning. In this paper we study the distributed version of this problem where we have multiple agents, and they want to learn the best arm collaboratively. We want to quantify the power of collaboration under limited interaction (or, communication steps), as interaction is expensive in many settings. We measure the running time of a distributed algorithm as the speedup over the best centralized algorithm where there is only one agent. We give almost tight round-speedup tradeoffs for this problem, along which we develop several new techniques for proving lower bounds on the number of communication steps under time or confidence constraints.