多腕バンディット問題における経験モーメントを用いた戦略
スポンサーリンク
概要
- 論文の詳細を見る
多腕バンディット問題は強化学習における知識の探索と活用のジレンマを定式化したもので,複数台のスロットマシンを選んでプレイするギャンブラーのモデルとして表される.本論文では各マシンからの reward が区間 [0,1] 上の確率分布にしたがう場合を考える。このモデルにおいては理論限界を漸近的に達成する戦略が知られているが、これは経験分布そのものを用いた凸最適化を毎回実行する必要がある。そこで本研究では任意の次数 d までの経験モーメントのみを用いて計算可能な戦略を新たに提案し、その性能が次数d を増やすことで理論限界に漸近することを示す。また、提案戦略においてはモーメント制約付きKL ダイバージェンス最小化を計算する必要があるが、これが Tchebycheff system の理論を用いることにより代数方程式系の求解に帰着できることを示す。
- 2011-08-29
著者
-
本多 淳也
東京大学大学院情報理工学系研究科
-
竹村 彰通
東京大学大学院情報理工学系研究科
-
竹村 彰通
東京大学大学院情報理工学系研究科:jst Crest
-
本多 淳也
東京大学大学院新領域創成科学研究科
-
竹村 彰通
東京大学大学院 情報理工学系研究科
関連論文
- LDPC符号と線形計画法を用いた情報源符号化(フレッシュマンセッション,フレッシュマンセッション,一般)
- F-1 母集団固有値が無限に発散したときのウィッシャート分布(分布論)(2003年度統計関連学会連合大会記録(日本統計学会第71回大会))
- チューブの体積と正規確率場の最大値の分布
- 複数の項目をもつ標本調査のための最適配分
- 実験計画法とグレブナー基底
- 計算代数統計の最近の話題について(日本統計学会賞受賞者特別寄稿論文)
- regularでない一部実施計画のあるクラスの性質(セッション3A,スタディー・グループ・セッション「計算機統計と計算代数の接点」)
- 統計学とグレブナー基底 : 計算代数統計の発端と展開
- コルモゴロフ生誕100年記念確率論数理統計学コンファレンス
- E-4 Characterization of Rankings Generated by Linear Discriminant Analysis(Summary of the Reports at the 71th Annual Meeting)
- D-2 混合分布モデルにおける一致推定量の構成(統計モデル)(2003年度統計関連学会連合大会記録(日本統計学会第71回大会))
- B-5 高次分割表のサンプリングのための不変極小基底(近似)(2003年度統計関連学会連合大会記録(日本統計学会第71回大会))
- B-2 Validity of the Expected Euler Characteristic Heuristic(Summary of the Reports at the 71th Annual Meeting)
- A-1 経験特性関数を用いたコーシー分布のGoodness-of-Fit Test(コンペティション(1))(2003年度統計関連学会連合大会記録(日本統計学会第71回大会))
- SIMULTANEOUS ESTIMATION OF THE MEANS IN SOME POISSON LOG LINEAR MODELS
- Characterization of Rankings Generated by Linear Discriminant Analysis
- 多腕バンディット問題における経験モーメントを用いた戦略
- 大学入試センター試験科目選択データの統計解析
- 高次分割表のサンプリングのための不変極小基底
- Validity of the expected Euler characteristic heuristic
- 個票開示問題の研究の現状と課題 (特集 個票開示問題の統計理論)
- A-2 2次元周辺度数を固定した3×3×K分割表上の既約なマルコフ基底の構成
- A-1 Some characterizations of minimal Markov basis for sampling from discrete conditional distributions
- 統計科学の今後の研究課題と科学研究費の申請について
- 2次元周辺度数を固定した3x3xK分割表上の既約なマルコフ基底の構成
- Some characterizations of minimal Markov basis for sampling from discrete conditional distributions
- B-4 層別抽出における最適配分 : 多変数の場合(官庁統計の現状と課題(3))(日本統計学会第69回大会記録)
- 多腕バンディット問題における経験モーメントを用いた戦略(テーマセッション,コンピュータビジョンとパターン認識のための機械学習)
- 多腕バンディット問題における経験モーメントを用いた戦略(テーマセッション,コンピュータビジョンとパターン認識のための機械学習)
- On a Non-Asymptotic Analysis Using Large Deviation Principles in the Multiarmed Bandit Problelm (情報論的学習理論と機械学習)
- 広がりのある統計学研究をめざして
- Homophonic Codeを用いた非対称通信路のFV符号化 (情報理論)
- A.M.Mathai,S.B.Provost and T.Hayakawa:Bilinear Forms and Zonal Polynomials
- 多腕バンディット問題における大偏差原理を用いた非漸近的解析について(機械学習一般とその応用)
- 二元分割表の副表和モデルに対するマルコフ基底(特別セッション 数理統計学の展開とその応用)
- Homophonic Codeを用いた非対称通信路のFV符号化(フレッシュマンセッション,一般)