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

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

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

这项研究旨在探索可实现效率的理论限制，并构建在多武器匪徒问题中实现这些理论限制的策略，这些策略对知识搜索和利用的困境进行了建模。这个问题已经很长一段时间了，近年来，它已经被积极研究，因为它可以直接应用于Web广告显示和网络路由等问题，但另一方面，先前研究中提出的策略仅保证了其对某些非常简单的概率分布模型的最佳性。因此，在今年的研究中，我们在一个非常普遍的非参数模型中得出了理论上的限制，其中仅知道奖励支持的下限，并提出了实现这一目标的策略。到目前为止，只有当概率分布的参数空间是一维或紧凑的时，并且很难将这些方法直接应用于本模型，这是无限的维度和非紧缩的，才知道理论极限的可实现性。但是，在这项研究中，我们通过解决最小化差异的双重问题来解决接近一维模型的问题来证明结果。此外，先前显示的渐近最佳策略在播放数的数量到O（log n）的损失方面是最佳的，但是高阶项与无限差异，尽管O（log n）。另一方面，各种研究在实验上表明，该高阶项可以用作O（1），并且常规理论研究和实验之间存在差距。因此，在这项研究中，我们新证明，在随机过程理论中，可以通过应用有关Martingale停止时间的结果来实现O（1）的损失。这项研究的结果目前已提交给《机器学习研究杂志》，这是一份有关机器学习的论文。

项目成果

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

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

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