非観測状態と制約された決定エポックを持つマルコフバンディットにおける学習

最近、arXivに投稿された論文「Learning in Markovian bandits with non-observable states and constrained decision epochs」（著者：Thomas Hira 他3名）は、状態が観測不可能で決定エポックが制約される可能性があるマルコフバンディットにおける後悔最小化問題を詳細に研究しています。従来のバンディットアルゴリズムは、各アームの状態を直接観測できるか、決定のタイミングに制限がないことを前提とすることが多いですが、現実の応用ではこれらの条件が満たされないことがよくあります。本論文は、「純粋」後悔ベンチマークに焦点を当て、学習アルゴリズムの性能を最適な純粋方策と比較します。純粋方策は、確率的バンディットの最適方策と同様に、最初から最後まで最適なアームを選択し続け、決して切り替えません。

まず、著者らは新しいバンディットモデルである自己劣化マルコフバンディット（self-degrading Markovian bandits）を導入します。これは、従来の静止マルコフバンディット（rested Markovian bandits）の一般化であり、各アームの状態は選択に応じて劣化し、純粋方策が常に漸近的に最適であることが示されています。この発見は、その後の理論解析の基盤を提供します。

論文の主要な理論的貢献は、事前知識が一切ない場合、アームをほとんど切り替えないアルゴリズムは必然的に超対数的な後悔（ω(log T)、Tは学習期間）を被ることを証明した点です。これは、古典的な対数後悔の限界がこの環境では達成不可能であることを意味します。しかし、著者らはUCB（上信頼限界）に着想を得た楽観的アルゴリズムUCB-NOMを設計し、ほぼ対数的な後悔を達成することで、理論と実践のギャップを埋めました。

さらに注目すべきは、アームのバイアス関数に関する境界という形で事前知識が与えられると、UCB-NOMは厳密にO(log T)の後悔を達成し、最悪の場合の後悔境界はO(√(T log T))となることです。これらの後悔境界は基礎となるマルコフ連鎖の状態数に依存せず、アルゴリズムの頑健性と拡張性を示しています。論文の結論は、自己劣化マルコフバンディットにおいて状態の非観測性は軽微な不便に過ぎず、適切に設計されたアルゴリズムと事前情報を用いることで最適に近い性能を得られることを示唆しています。この研究は、推薦システム、動的価格設定、臨床試験などの応用に重要な理論的指針を提供します。