要旨: 私たちは、k-腕の確率的バンディット問題に対する方策勾配の連続時間拡散近似を研究する。私たちは、学習率 \\eta = O(\\Delta^2/\\log(n)) のとき、後悔は O(k \\log(k) \\log(n) / \\eta) になることを証明する。ここで n はホライズン、\\Delta は最小ギャップである。さらに、腕数が対数的にしか多くないインスタンスを構築し、\\eta が O(\\Delta^2) でない限り後悔は線形になることを示す。
確率的バンディットの方策勾配に対する拡散分析
arXiv cs.AI / 2026/3/12
📰 ニュースIdeas & Deep AnalysisModels & Research
要点
- 著者らは、k腕の確率的バンディット問題に対する方策勾配の連続時間拡散近似を研究している。
- 学習率 $\\eta = O(\\Delta^2/\\log(n))$ のとき、後悔は $O(k \\log(k) \\log(n) / \\eta)$ になることを証明する。ここで $n$ はホライズン、$\\Delta$ は最小ギャップである。
- 対数的に少ない腕数しか持たないインスタンスを構築し、$\\eta$ = O($\\Delta^2$) でない限り後悔が線形になる。
- 結果は、拡散ベースの方策勾配法における探索と後悔のバランスを取る学習率の選択に指針を提供する。
