期刊
MATHEMATICS OF OPERATIONS RESEARCH
卷 35, 期 2, 页码 395-411出版社
INFORMS
DOI: 10.1287/moor.1100.0446
关键词
multi-armed bandit; parametric model; adaptive control
资金
- National Science Foundation [DMS-0732196, ECCS-0701623, CMMI-0856063, CMMI-0855928]
- Div Of Civil, Mechanical, & Manufact Inn
- Directorate For Engineering [1158658, 0746844] Funding Source: National Science Foundation
- Div Of Civil, Mechanical, & Manufact Inn
- Directorate For Engineering [1158659, 0856063, 0855928] Funding Source: National Science Foundation
We consider bandit problems involving a large (possibly infinite) collection of arms, in which the expected reward of each arm is a linear function of an r-dimensional random vector Z is an element of R-r, where r >= 2. The objective is to minimize the cumulative regret and Bayes risk. When the set of arms corresponds to the unit sphere, we prove that the regret and Bayes risk is of order Theta(r root T), by establishing a lower bound for an arbitrary policy, and showing that a matching upper bound is obtained through a policy that alternates between exploration and exploitation phases. The phase-based policy is also shown to be effective if the set of arms satisfies a strong convexity condition. For the case of a general set of arms, we describe a near-optimal policy whose regret and Bayes risk admit upper bounds of the form O(r root T log(3/2) T).
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据