本論文は、状態が観測不可能で意思決定時点が制限される可能性のあるマルコフ多腕バンディット問題における後悔最小化の研究です。研究の焦点は「純粋」な後悔ベンチマークに当てられており、これは学習アルゴリズムの性能を、最初から最後まで常に最適なアームを選択し続ける純粋ポリシー（確率的バンディットの最適ポリシーに類似）と比較するものです。 著者らは休止型マルコフバンディットの一般化として「自己劣化型マルコフバンディット」を導入し、この設定では純粋ポリシーが常に漸近的に最適であることを示しています。基盤となるバンディットについの事前知識がない場合、アームの切り替え頻度が低いアルゴリズムの後悔は、学習期間Tに対してω(log(T))というスーパー対数スケールで増加することを証明しました。 対数領域の到達不可能性にもかかわらず、著者らはUCBに着想を得た最適化アルゴリズム「UCB-NOM」を設計し、ほぼ対数的な後悔を達成しています。さらに、アームのバイアス関数の境界という形でマルコフバンディットに関する事前知識が与えられた場合、UCB-NOMの適切なインスタンス化はO(log(T))の後悔を実現します。この事前知識により、UCB-NOEは最悪ケースでO(√T log(T))の後悔境界も達成可能です。特に注目すべき点として、提案された後悔境界はマルコフ連鎖の状態数に依存していません。これらの知見は、状態の観測不可能性が自己劣化型マルコフバンディットにおいて比較的軽微な課題であることを示唆しています。