| 講演名 | 2009-09-14 複数アクションを選択するAdversarial Bandit問題について 打矢 泰志, 中村 篤祥, 工藤 峰一, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | Auerらにより研究されたadversarial bandit問題は,プレーヤーが選択したアクションに対する報酬生成過程において確率的な仮定をおかないmulti-armed bandit問題である.本稿ではadversarial bandit問題を,各時刻においてk(≧1)回のアクションを選択できるように拡張し,アクションの重複選択を許す場合と許さない場合の2つの設定で分析を行う.両方の設定において,Auerらが提案したアルゴリズムExp3を一般化し,最適固定アクション集合に対する損失上界の一般化を得る. |
| 抄録(英) | Adversarial bandit problems studied by Auer et al. are the multi-armed bandit problems in which no stochastic assumption is made on the nature of the process generating the rewards for actions. In this paper, we extend their theories to those in the case when k(≧1) actions are selected at each time step. We analyze the problems in two settings of multiple plays, that is, in the settings of selections with and without repetition. In the both settings, we generalize the Exp3 family algorithms developed by them and give the generalized upper bounds on the regrets for the best fixed set of actions. |
| キーワード(和) | multi-armed bandit問題 / adversarial bandit問題 / オンライン学習アルゴリズム |
| キーワード(英) | multi-armed bandit problem / adversarial bandit problem / online learning |
| 資料番号 | COMP2009-27 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2009/9/7(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 複数アクションを選択するAdversarial Bandit問題について |
| サブタイトル（和） | |
| タイトル（英） | Adversarial Bandit Problems with Multiple Plays |
| サブタイトル（和） | |
| キーワード(1)（和/英） | multi-armed bandit問題 / multi-armed bandit problem |
| キーワード(2)（和/英） | adversarial bandit問題 / adversarial bandit problem |
| キーワード(3)（和/英） | オンライン学習アルゴリズム / online learning |
| 第 1 著者 氏名（和/英） | 打矢 泰志 / Taishi UCHIYA |
| 第 1 著者 所属（和/英） | 北海道大学大学院情報科学研究科 Graduate School of Information Science and Technology Hokkaido University |
| 第 2 著者 氏名（和/英） | 中村 篤祥 / Atsuyoshi NAKAMURA |
| 第 2 著者 所属（和/英） | 北海道大学大学院情報科学研究科 Graduate School of Information Science and Technology Hokkaido University |
| 第 3 著者 氏名（和/英） | 工藤 峰一 / Mineichi KUDO |
| 第 3 著者 所属（和/英） | 北海道大学大学院情報科学研究科 Graduate School of Information Science and Technology Hokkaido University |
| 発表年月日 | 2009-09-14 |
| 資料番号 | COMP2009-27 |
| 巻番号（vol） | vol.109 |
| 号番号（no） | 195 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |