Arrow Research search

Author name cluster

Xi Chen 0010

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

6 papers
1 author row

Possible papers

6

ICML Conference 2017 Conference Paper

Adaptive Multiple-Arm Identification

  • Jiecao Chen
  • Xi Chen 0010
  • Qin Zhang 0001
  • Yuan Zhou 0007

We study the problem of selecting K arms with the highest expected rewards in a stochastic n-armed bandit game. This problem has a wide range of applications, e. g. , A/B testing, crowdsourcing, simulation optimization. Our goal is to develop a PAC algorithm, which, with probability at least $1-\delta$, identifies a set of K arms with the aggregate regret at most $\epsilon$. The notion of aggregate regret for multiple-arm identification was first introduced in Zhou et. al. (2014), which is defined as the difference of the averaged expected rewards between the selected set of arms and the best K arms. In contrast to Zhou et. al. (2014) that only provides instance-independent sample complexity, we introduce a new hardness parameter for characterizing the difficulty of any given instance. We further develop two algorithms and establish the corresponding sample complexity in terms of this hardness parameter. The derived sample complexity can be significantly smaller than state-of-the-art results for a large class of instances and matches the instance-independent lower bound up to a $\log(\epsilon^{-1})$ factor in the worst case. We also prove a lower bound result showing that the extra $\log(\epsilon^{-1})$ is necessary for instance-dependent algorithms using the introduced hardness parameter.

Details

SODA Conference 2017 Conference Paper

Competitive analysis of the top- K ranking problem

  • Xi Chen 0010
  • Sivakanth Gopi
  • Jieming Mao
  • Jon Schneider

Motivated by applications in recommender systems, web search, social choice and crowdsourcing, we consider the problem of identifying the set of top K items from noisy pairwise comparisons. In our setting, we are non-actively given r pairwise comparisons between each pair of n items, where each comparison has noise constrained by a very general noise model called the strong stochastic transitivity (SST) model. We analyze the competitive ratio of algorithms for the top- K problem. In particular, we present a linear time algorithm for the top- K problem which has a competitive ratio of i. e. to solve any instance of top -K, our algorithm needs at most times as many samples needed as the best possible algorithm for that instance (in contrast, all previous known algorithms for the top- K problem have competitive ratios of Ω( n ) or worse). We further show that this is tight: any algorithm for the top- K problem has competitive ratio at least

Details

ICML Conference 2014 Conference Paper

Optimal PAC Multiple Arm Identification with Applications to Crowdsourcing

  • Yuan Zhou 0007
  • Xi Chen 0010
  • Jian Li 0015

We study the problem of selecting K arms with the highest expected rewards in a stochastic N-armed bandit game. Instead of using existing evaluation metrics (e. g. , misidentification probability or the metric in EXPLORE-K), we propose to use the aggregate regret, which is defined as the gap between the average reward of the optimal solution and that of our solution. Besides being a natural metric by itself, we argue that in many applications, such as our motivating example from crowdsourcing, the aggregate regret bound is more suitable. We propose a new PAC algorithm, which, with probability at least 1-δ, identifies a set of K arms with regret at most ε. We provide the sample complexity bound of our algorithm. To complement, we establish the lower bound and show that the sample complexity of our algorithm matches the lower bound. Finally, we report experimental results on both synthetic and real data sets, which demonstrates the superior performance of the proposed algorithm.

Details
v2026.09.13