【要約】「そろそろ攻めるか」を勘で決めない。UCBとThompson samplingをε-greedyと競走させた [Zenn_Python] | Summary by TechDistill
> Source: Zenn_Python
Execute Primary Source
// Problem
開発者が多腕バンディット問題において、探索と活用のバランスを決定する際に直面する課題を整理した。従来の単純な手法では、学習が進んだ後も無駄な試行を繰り返してしまう問題がある。
- ・ε-greedyは探索率が固定されるため、最適解が判明した後も探索を止められない。
- ・「今どれくらい迷っているか」という不確実性を、探索の強度に反映できていない。
- ・探索の割合を勘や固定パラメータに頼るため、学習状況に最適化できない。
// Approach
不確実性を指標として探索を自動化する2つの手法を実装し、ε-greedyとの比較実験を行った。各手法がどのように「迷い」を計算し、選択に反映させるかを検証している。
- ・UCB: 推定値に不確実性に基づくボーナスを加算し、楽観的に選択を行う。
- ・Thompson sampling: 事後分布から乱数をサンプリングし、信念に基づき選択を行う。
- ・10本腕ガウスバンディットを用い、1000回の試行で累積後悔を測定した。
// Result
1000回の独立試行による実験の結果、各手法の累積後悔と最適腕選択率の差が明らかになった。手法によって、学習が進むにつれての「後悔の伸び方」が劇的に異なる。
- ・Thompson samplingが累積後悔79を記録し、最も優れた性能を示した。
- ・ε-greedyは探索を止められず、後悔が直線的に増大し続けた。
- ・UCBは全腕を試すコストにより、序盤250ステップではε-greedyに劣る。
Senior Engineer Insight
> 実戦では、評価期間の設定が勝敗を分ける。Thompson samplingは長期的な収益最大化に極めて強い。一方で、UCBのように序盤に探索コストを支払う手法もある。システムの目的が「初動の安定」か「長期的な最適化」かを見極めよ。ε-greedyのような固定探索は、運用コストの観点から避けるべきだ。