登入選單

返回Google圖書搜尋

An Asymptotically Optimal Algorithm for the Max K-armed Bandit Problem

Matthew J. Streeter

出版	School of Computer Science, Carnegie Mellon University, 2006
URL	http://books.google.com.hk/books?id=I8MbtwAACAAJ&hl=&source=gbs_api

註釋

Abstract: "We present an asymptotically optimal algorithm for the max variant of the k-armed bandit problem. Given a set of k slot machines, each yielding payoff from a fixed (but unknown) distribution, we wish to allocate trials to the machines so as to maximize the expected maximum payoff received over a series of n trials. Subject to certain distributional assumptions, we show that O((ln(1/[delta]) ln(n)2/[epsilon]2)) trials are sufficient to identify, with probability at least 1-[delta], a machine whose expected maximum payoff is within [epsilon] of optimal. This result leads to a strategy for solving the problem that is asymptotically optimal in the following sense: the gap between the expected maximum payoff obtained by using our strategy for n trials and that obtained by pulling the single best arm for all n trials approaches zero as n -> [infinity]."