文献

J-GLOBAL ID：201202254172432238   整理番号：12A1064302

多腕バンディット問題における大偏差原理を用いた非漸近的解析について

On a Non-asymptotic Analysis Using Large Deviation Principles in the Multiarmed Bandit Problem

著者 (2件)： HONDA Junya (Univ. Tokyo, Chiba, JPN) ,  TAKEMURA Akimichi (Univ. Tokyo, Tokyo, JPN)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 112  号： 83(IBISML2012 1-12)  ページ： 65-72  発行年： 2012年06月12日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 短報  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 多腕バンディット問題は強化学習における知識の探索と活用のジレンマを定式化したもので,複数台のスロットマシンを選んでプレイするギャンブラーのモデルとして表される。本論文では各マシンからの報酬が区間[0,1]上の確率分布にしたがう場合をまず考える。このモデルにおいて理論限界を達成するものとしてDMED戦略が近年提案されたが,その評価は漸近論に大きく依存しており有限試行回数での性能評価は知られていない。そこで本研究ではKLダイバージェンスの挙動に関する漸近形でない大偏差原理を導出することによりDMED戦略の有限試行回数での性能評価を行う。さらに,報酬の分布のサポートが下側が非有界の場合であっても積率母関数が存在する場合には理論限界を達成可能であることを合わせて示す。(著者抄録)

シソーラス用語： *強化学習 ,  モデリング ,  定式化 ,  性能評価 ,  賃金 ,  人間行動 ,  確率分布 ,  エントロピー ,  情報量 ,  インセンティブ
準シソーラス用語： Kullback-Leiblerダイバージェンス ,  ギャンブル ,  ジレンマ ,  モデル化 ,  報酬

分類 (1件)： 人工知能  (JE08000Z)

引用文献 (17件)：

• GITTINS, J. C. Multi-armed bandit allocation indices. 1989
• AGRAWAL, R. The continuum-armed bandit problem. SIAM Journal on Control and Optimization. 1995, 33, 6, 1926-1951
• AUER, P. The nonstochastic multiarmed bandit problem. SIAM Journal on Computing. 2002, 32, 1, 48-77
• ROBBINS, H. Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Society. 1952, 58, 5, 527-535
• LAI, T. L. Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics. 1985, 6, 4-22

タイトルに関連する用語 (3件)： 腕 ,  大偏差原理 ,  解析