多腕バンディット問題における最適戦略の構成と発展

多臂老虎机问题最优策略的构建和发展

• 批准号: 25880006
• 负责人: 本多 淳也
• 金额: $ 1.58万
• 依托单位: The University of Tokyo
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Research Activity Start-up
• 财政年份: 2013
• 资助国家: 日本
• 起止时间: 2013-08-30 至 2015-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-25880006/
• 关键词: 機械学習; 統計学; 多腕バンディット問題

本研究は，知識の探索と活用のジレンマをモデル化したものである多腕バンディット問題において，達成可能な効率の理論限界を探り，またその理論限界を達成する戦略を具体的に構成することを目標に行った．この問題は古くから知られており，特に近年ではウェブ上の広告表示やネットワークルーティングといった問題に直接応用できることから盛んに研究されているが，一方，従来研究で提案された戦略でその最適性が保証されているのは一部の非常に単純な確率分布モデルに限られていた．そこで本年度の研究においては，報酬のサポートの下限のみが既知という極めて一般的なノンパラメトリックモデルにおける理論限界を導出し，さらにそれを達成する戦略の提案を行った．これまでに理論限界の達成可能性が知られていたのは確率分布のパラメータ空間が１次元あるいはコンパクトな場合に限られており，それらの手法を無限次元かつ非コンパクトである今回のモデルに直接適用するのは困難であったが，本研究ではダイバージェンス最小化の双対問題を経由して１次元モデルに近い問題への帰着を行うことにより証明を行った．さらに，従来示されていた漸近最適戦略は，プレイ回数nに対する損失のうちO(log n)の項までの意味では最適であったが，それより高次の項がo(log n)ではあるものの無限大に発散するものであった．一方，この高次項はO(1)とできることが様々な研究から実験的には示唆されており，この点で従来の理論研究と実験の間にはギャップがあった．そこで，本研究では確率過程の理論のうちマルチンゲールの停止時刻に関する結果を応用することで，O(1)の損失が達成可能であることを新たに示した．この研究の結果は機械学習の論文誌Journal of Machine Learning Researchに現在投稿中である．

This study aims to explore the application of knowledge and to explore the theoretical limits of the possibility of achieving the theoretical limits. This problem has been solved in the past, especially in recent years. The problem of direct application has been solved in the past. On the one hand, the problem of optimization has been solved in the future. On the other hand, the problem of extreme purity has been solved in the future. This year's study is aimed at deriving the theoretical limits of compensation from the known lower limit of compensation and achieving the proposed strategy. The probability of reaching the theoretical limit is known, the accuracy of the distribution is determined, the space is 1-dimensional, the method is infinite, the time is not constant, and the method is directly applicable. In this paper, we study the problem of minimizing the two-dimensional problem from the first dimension to the second dimension. The term O(log n) of the loss is the optimal term, and the term O(log n) of the higher order is the optimal term. A party, the higher order term O(1) This paper presents a new method for determining the theoretical value of the probability process. Journal of Machine Learning Research.

项目成果

知識の探索と活用のジレンマと多腕バンディット問題

知识探索与利用的困境与多臂老虎机问题

• 发表时间: 2013
• 作者: Mianxiong Dong;Kaoru Ota;and Motoki Sakai;本多淳也
• 通讯作者: 本多淳也