| 講演名 | 2011-09-05 多腕バンディット問題における経験モーメントを用いた戦略(テーマセッション,コンピュータビジョンとパターン認識のための機械学習) 本多 淳也, 竹村 彰通, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 多腕バンディット問題は強化学習における知識の探索と活用のジレンマを定式化したもので、複数台のスロットマシンを選んでプレイするギャンブラーのモデルとして表される。本論文では各マシンからのrewardが区間[0,1]上の確率分布にしたがう場合を考える。このモデルにおいては理論限界を漸近的に達成する戦略が知られているが、これは経験分布そのものを用いた凸最適化を毎回実行する必要がある。そこで本研究では任意の次数dまでの経験モーメントのみを用いて計算可能な戦略を新たに提案し、その性能が次数dを増やすことで理論限界に漸近することを示す。また、提案戦略においてはモーメント制約付きKLダイバージェンス最小化を計算する必要があるが、これがTchebycheff systemの理論を用いることにより代数方程式系の求解に帰着できることを示す。 |
| 抄録(英) | In the multiarmed bandit problem a gambler chooses an arm of a slot machine to pull considering a tradeoff between exploration and exploitation. We study the stochastic bandit problem where each arm has a reward distribution supported in a known bounded interval, e.g. [0,1]. For this model, there exists a policy which achieves the theoretical bound asymptotically. However the optimal policy requires a computation of a convex optimization which involves the empirical distribution of each arm. In this paper, we propose a policy which exploits the first d empirical moments for arbitrary d fixed in advance. The asymptotic upper bound of the regret of the policy approaches the theoretical bound as d increases. The proposed policy requires a minimization of KL divergence with moment constraints. We show by the theory of Tchebycheff system that the optimal value is obtained by solving polynomial equations. |
| キーワード(和) | 多腕バンディット問題 / Tchebycheff system / moment space / ダイバージェンス最小化 |
| キーワード(英) | multiarmed bandit problem / Tchebycheff system / moment space / divergence minimization |
| 資料番号 | PRMU2011-60,IBISML2011-19 |
| 発行日 |
| 研究会情報 | |
| 研究会 | PRMU |
|---|---|
| 開催期間 | 2011/8/29(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Pattern Recognition and Media Understanding (PRMU) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 多腕バンディット問題における経験モーメントを用いた戦略(テーマセッション,コンピュータビジョンとパターン認識のための機械学習) |
| サブタイトル（和） | |
| タイトル（英） | Multiarmed Bandit Algorithms Based on Empirical Moments |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 多腕バンディット問題 / multiarmed bandit problem |
| キーワード(2)（和/英） | Tchebycheff system / Tchebycheff system |
| キーワード(3)（和/英） | moment space / moment space |
| キーワード(4)（和/英） | ダイバージェンス最小化 / divergence minimization |
| 第 1 著者 氏名（和/英） | 本多 淳也 / Junya HONDA |
| 第 1 著者 所属（和/英） | 東京大学大学院新領域創成科学研究科 Graduate School of Frontier Sciences, The University of Tokyo |
| 第 2 著者 氏名（和/英） | 竹村 彰通 / Akimichi TAKEMURA |
| 第 2 著者 所属（和/英） | 東京大学大学院情報理工学系研究科 Graduate School of Information Science and Technology, The University of Tokyo |
| 発表年月日 | 2011-09-05 |
| 資料番号 | PRMU2011-60,IBISML2011-19 |
| 巻番号（vol） | vol.111 |
| 号番号（no） | 193 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |