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

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

• 批准号: 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に現在投稿中である．

本研究探讨了多臂老虎机问题中可实现效率的理论极限，对知识探索和利用的困境进行了建模，并具体构建了实现理论极限的策略。这个问题早已为人所知，并且近年来得到了积极的研究，因为它可以直接应用于网络上的广告显示和网络路由等问题。保证仅限于一些非常简单的概率分布模型。因此，在今年的研究中，我们推导了一种极其通用的非参数模型（仅已知奖励支持的下限）的理论极限，并进一步提出了实现这些模型的策略。到目前为止，只有当概率分布的参数空间为一维或紧致时，才知道实现理论极限的可行性，并且这些方法可以直接应用于当前的无限维和非连续模型。尽管它很难应用，但在本研究中，我们通过散度最小化的对偶问题将其简化为接近一维模型的问题来证明它。此外，之前提出的渐近最优策略对于播放次数 n 而言，在损失高达 O(log n) 方面是最优的，但高阶项是 o(log n) ，它是趋于无穷大的。另一方面，各种研究通过实验表明这个高阶项可以是O(1)，在这方面传统的理论研究和实验之间存在差距。因此，在这项研究中，我们新表明，通过应用随机过程理论中鞅停止时间的结果，可以实现 O(1) 的损失。这项研究的结果目前正在提交给《机器学习研究杂志》。

项目成果

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

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

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