技術要約：非観測状態および制約付き決定エポックにおけるマルコフ的バンディットの学習

1. 問題定義

本論文は、以下の2つの特定の制約下における**マルコフ的バンディット（Markovian bandits）**のレグレット最小化問題を取り扱う。

1. 非観測状態（Non-observable States）: コントローラーはアームの内部状態（マルコフ連鎖）を観測できない。利用可能なフィードバックは、活性化されたアームによって生成される報酬のみである。これは、状態空間が隠れた「フル・バンディット・フィードバック」の設定に対応する。
2. 制約付き決定エポック（Constrained Decision Epochs）: コントローラーは、すべてのタイムステップで任意にアームを切り替えることはできない。代わりに、切り替えは報酬のストリームによって決定される特定の決定エポック（$\tau_i$、停止時間）においてのみ許可される。具体的には、コントローラーはある特定の信号（例：非ゼロの報酬）を受け取るまで、そのアームに留まり続けなければならない。

アームはマルコフ決定過程（MDP）としてモデル化されており、遷移ダイナミクスは、そのアームが活性（active）か非活性（passive）かに依存する。システムは、非活性のアームが受動的カーネル（$p^0_a$）に従って遷移し、活性化されたアームが能動的カーネル（$p^1_a$）に従って遷移するように進化する。

2. 学習フレームワークとベンチマーク

著者らは、分析対象を**「純粋レグレット（pure regret）」**ベンチマークに限定している。

• 純粋方策（Pure Policies）: 方策が「純粋」であるとは、学習ホライゾンの開始から終了まで、一度も切り替えることなく単一のアームを選択し続けることを指す。
• レグレットの定義: レグレットは、学習アルゴリズムの累積報酬と、最良の純粋方策（漸近的な利得が最も高いアーム）の累積報酬との差として定義される。

純粋方策の動機:
レストレス・バンディット（非活性のアームも進化する設定）において、純粋方策は一般に劣最適であるが、著者らは**自己劣化型レストレス・バンディット（self-degrading restless bandits）**と呼ばれるクラスを導入している。この場合、アームが非活性の状態にあると、その期待バイアス（平均報酬からの偏差の尺度）は、コントローラーの観測に対して減少または一定に保たれる。本論文は、自己劣化型バンディットにおいては、純粋方策が漸近的に最適であることを証明している。このクラスは、レスト（静止）バンディット（非活性のアームが凍結する設定）を一般化したものであり、非プリエンプティブなGilbert-ElliottチャネルやNerlove-Arrowモデルのような非自明なレストレス・モデルを含んでいる。

3. 手法：UCB-NOM

本論文では、UCB原理に着想を得た楽観的なアルゴリズムであるUCB-NOM（Upper Confidence Bound for Non-Observable Markovian bandits）を提案している。

UCB-NOMの主要構成要素:

1. 経験的利得推定器（Empirical Gain Estimator）: アルゴリズムは、当該アームが活性であったときに収集された報酬を平均することで、アームの利得（$g_a$）を推定する。
2. 楽観的インデックスの構築: 非観測性と制約を処理するために、アルゴリズムは真の利得に対する楽観的な上限 $\tilde{g}_a(t)$ を構築する。このインデックスには以下が含まれる：
   • 経験的な平均報酬。
   • 以下の要素を考慮した探索ボーナス（信頼区間）：
     • プル回数（$N_a(t)$）。
     • アルゴリズムがアーム $a$ へ切り替えた回数（スイッチング・コスト）。
     • アームのバイアス・スパン（bias span）（$sp(b_a)$）：バイアス関数の最大偏差を定量化するもの。
3. 倍増トリック（Doubling Trick）: 理論的な保証に必要な「稀な切り替え」の特性を満たすため、アルゴリズムは倍増トリックを採用する。一度アームが選択されると、その訪問回数が倍増するまでプレイし続ける。これにより、スイッチの回数がプルの回数に対して対数的に成長することを保証する。

対処された理論的課題:

• 非観測性: 再生サイクルをトリガーするために状態の観測に依存する先行研究（Tekin & LiuによるRCAなど）とは異なり、UCB-NOMは再生を利用できない。代わりに、バイアス・スパンとスイッチ回数を用いて誤差を抑え込む。
• 制約付きエポック: アルゴリズムは、決定エポック間の遅延を考慮しなければならない。分析では、次の決定エポックまでの期待時間に対して境界（$C_\tau$）を仮定している。

4. 主要な結果と理論的保証

A. 下界（対数レグレットの不可能性）

バンディットの構造に関する事前知識がない場合、一貫性のある稀な切り替えアルゴリズムにとって、対数レグレット（$O(\log T)$）は達成不可能であることを本論文は確立している。

• 定理 4: 一貫性のある稀な切り替えアルゴリズムに対して、期待レグレットは $\omega(\log T)$（超対数的）となる。これは、報酬のみを通じて真のモデルと区別がつかない代替モデルを構築することで証明される。このモデルでは、アルゴリズムが劣劣なアームを過度に引き続けざるを得ない状況を作り出し、最適なアームを特定することを困難にする。

B. UCB-NOMの性能（一般ケース）

• 定理 6: UCB-NOMは、$O(f(T)^2 \log T)$ のレグレット境界を達成する。ここで $f(T)$ は無限大に発散する「スパン・プロキシ（span proxy）」関数である。
• 意義: $f(T)$ を任意に遅く発散するように選択することで、UCB-NOMは理想的な対数領域に限りなく近づけることができ、実質的に超対数的な下界に一致させることができる。

C. 事前知識がある場合の性能（有界バイアス・スパン）

アルゴリズムに、すべてのアームのバイアス・スパンの上限 $D$ および決定エポックの遅延に関する既知の情報が与えられている場合、性能は大幅に向上する。

• 定理 8（インスタンス依存）: 固定されたスパン・プロキシ $f \equiv D$ を用いる場合、UCB-NOMは $O(\log T)$ のインスタンス依存レグレットを達成する。
• 定理 9（ワーストケース）: 同様の有界スパン仮定の下で、アルゴリズムは $O(\sqrt{T \log T})$ のワーストケース・レグレットを達成する。

D. チューニングと信頼パラメータ

本論文は、信頼パラメータ $\delta(t)$ の選択について分析している。マルコフ的な設定においては、確率的バンディットと比較して、「過小に楽観的（under-optimistic）」になること（より大きな信頼区間を持つために、より小さな $\delta(t)$ を選択すること）が好ましいと示唆している。これは、バイアス・スパンのために、マルコフ的推定子のノイズが報酬の分散よりも大きくなる可能性があり、楽観的な性質を維持するためにより大きな探索ボーナスが必要となるためである。

5. 意義と貢献

本論文は、以下の貢献を主張している。

1. 問題の定式化: 通信ネットワーク（例：非プリエンプティブなチャネル・スケジューリング）を動機として、非観測状態と内生的な制約付き決定エポックを組み合わせた学習設定を定式化した。
2. 自己劣化型バンディット: 純粋方策が最適となるレストレス・バンディットのクラスを特定・定義し、純粋レグレットをベンチマークとして使用することの正当性を与えた。
3. 基本的限界: 状態の非観測性と制約付きエポックの組み合わせが、一般の場合において対数レグレットを本質的に妨げることを証明し、超対数的な下界を確立した。
4. アルゴリズム設計: UCB-NOMを導入し、状態の観測なしに最適に近いレグレットを達成できることを示した。決定的なのは、レグレット境界が基礎となるマルコフ連鎖の状態数（$|S_a|$）ではなく、バイアス・スパンに依存している点である。
5. 構造的洞察: 単純な事前知識（バイアス・スパンの境界）があれば、古典的な確率的バンディットの対数レグレットの保証を回収できることを示しており、これは、自己劣化的な設定においては、状態の非観測性が（構造的境界が既知であれば）「軽微な不便さ」に過ぎないことを示唆している。

著者らは、この設定は標準的な確率的バンディットよりも複雑であるが、提案されたフレームワークとアルゴリズムは、自己劣化的な設定において純粋レグレットのベンチマークに従う限り、部分観測マルコフ決定過程（POMDP）に伴う複雑な手法を必要とせずに、堅牢な理論的保証を提供すると結論付けている。