技術要約：Flickering Multi-Armed Bandits (明滅する多腕バンディット)

1. 問題の定式化

本論文は、エージェントの現在状態に依存してアクションの可用性が動的かつ制限される環境における逐次的意思決定に対処するため、Flickering Multi-Armed Bandit (FMAB) フレームワークを導入している。固定された一連の腕（アーム）への無制限なアクセスを仮定する古典的な Multi-Armed Bandit (MAB) 問題とは異訳、FMAB は、エージェントが確率的に進化するグラフ内での現在の位置によって定義される、利用可能な腕のサブセットからのみ選択できるシナリオをモデル化している。

核となる制約:

• 局所的なアクセシビリティ (Local Accessibility): 各ラウンド $t$ において、エージェントは腕 $a_{t-1}$ に滞在している。利用可能な腕の集合 $L_t(a_{t-1})$ は、現在のグラフ $G_t$ における $a_{t-1}$ の近傍、および現在の腕自身に限定される。
• 確率的な進化 (Stochastic Evolution): グラフ $G_t$ は時間の経過とともに進化する。エージェントは任意の腕へ自由にジャンプすることはできず、未訪問または有望な腕に到達するためにグラフ構造をナビゲートしなければならない。
• 二重の課題 (Dual Challenge): エージェントは、統計的な情報獲得（最適な腕を特定するための探索）と、物理的なナビゲーション・オーバーヘッド（グラフを通じてそれらの腕に移動するためのコスト）の間の緊張関係に直面する。

グラフモデル:
著者らは、アクションの可用性の進化を、主に2つのランダムグラフプロセスを通じて定式化している。

1. i.i.d. Erdős–Rényi (ER): 各ラウンドで、新しいグラフが独立にサンプリングされる。エッジは確率 $p$（均質）またはエッジ固有の確率 $p_{ij}$（不均質）で存在する。
2. Edge-Markovian (エッジ・マルコフ的): グラフは前の状態から進化する。エッジは確率 $\alpha$ で出現し、確率 $\beta$ で消失する。これは、トポロジーが完全にリセットされるのではなく、緩やかに変化する「粘着性のある」接続性をモデル化している。

目的は、これらの局所移動制約の下で、累積リグレット $R(T) = \sum_{t=1}^T (\mu(a^*) - r_t(a_t))$ を最小化することである（ここで $a^*$ は最適な腕である）。

2. 手法

提案される解は、Lazy Random Walk (怠惰なランダムウォーク) を用いた探索を利用する 二段階学習アルゴリズム (Two-Phase Learning Algorithm) である。

フェーズ I: 最良腕の特定 (探索)

• 方策 (Policy): エージェントは怠惰なランダムウォークを実行する。各ステップにおいて、現在の腕 $a_{t-1}$ と実現したグラフ $G_t$ が与えられたとき、エージェントは利用可能な集合 $L_t(a_{t-1})$ から一様にランダムに次の腕 $a_t$ を選択する。
• 期間: このフェーズは、あらかじめ決定された時間 $T_0$ 続く。
• 目的: すべての腕から十分なサンプルを収集し、それらの平均報酬 $\hat{\mu}(a)$ を正確に推定することである。
• 終了: フェーズ I の終了時に、エージェントは候補となる最適腕 $\hat{a}^* = \arg\max_a \hat{\mu}(a)$ を特定する。

フェーズ II: ナビゲーションとコミットメント (活用)

• 方策: エージェントは、特定されたターゲット $\hat{a}^*$ に到達するまで、怠惰なランダムウォークを継続する。
• コミットメント: エージェントが $\hat{a}^*$ に着地すると、以降のすべてのラウンドにおいてこの腕にコミットする。エージェントは常に現在の腕に留まることができる（自己ループ）ため、$\hat{a}^*$ に永久に留まり続けることができる。

理論的分析手法

その分析は、進化するマルコフ連鎖のスペクトル技術と、時変グラフに対する集中不等式を橋渡しするものである。

• i.i.d. ER グラフの場合:
  • 均質ケース: 期待遷移カーネルは対称かつ二重確率的であり、一様な定常分布をもたらす。著者らは、ウォークが効率的に混合することを示すために再生引数 (regeneration argument) を用いている。
  • 不均質ケース: カーネルは対称ではない。著者らは一様典型性引数 (uniform typicality argument) を採用し、実現されたグラフの特性（次数、カット）が期待値の周囲に鋭く集中することを証明し、スペクトルギャップと定常分布に関する一様な境界を導出している。
• Edge-Markovian グラフの場合:
  • 分析は、エージェントのウォークとグラフの進化との間の結合に対処する。
  • 「二速度 (Two Speeds)」条件が確立されている：グラフは、ランダムウォークの混合速度に対して十分に遅く進化しなければならない（粘着性条件 $\beta \le O(1/n)$）。
  • アルゴリズムは、標準的な探索フェーズを開始する前に、グラフプロセスが定常分布に達するためのバーンイン期間 ($T_{burn}$) を必要とする。

3. 主要な結果

リグレット境界

本論文は、両方のグラフモデルに対して高確率な劣線形リグレット境界を確立している。

定理 1 (i.i.d. ER グラフ):
不均質な ER モデルにおいて、リグレット $R(T)$ は確率 $1-\delta$ で以下を満たす：
$$R(T) \le \underbrace{O\left(n \log(nT/\delta) + \frac{n \log(n/\delta)}{\Delta_{\min}^2}\right)}_{\text{探索コスト}} + \underbrace{O\left(n \log(n/\delta)\right)}_{\text{ナビゲーションコスト}}$$
ここで $\Delta_{\min}$ は最小の劣最適性ギャップである。探索コストは腕の数 $n$ に対して線形にスケールし、ナビゲーションコストは最適な腕に到達するまでの時間を考慮している。

定理 3 (Edge-Markovian グラフ):
典型性と粘着性の条件下では、リグレットには追加のバーンイン項が含まれる：
$$R(T) \le \underbrace{O\left(\frac{\log(nT/\delta)}{\alpha+\beta}\right)}_{\text{バーンイン}} + \underbrace{O\left(n \log(nT/\delta) + \frac{n \log(n/\delta)}{\Delta_{\min}^2}\right)}_{\text{探索}} + \underbrace{O\left(n \log(n/\delta)\right)}_{\text{ナビゲーション}}$$

期待リグレットと近最適性

失敗確率 $\delta = 1/T$ と設定することで、著者らは期待リグレット境界を導出している：
$$E[R(T)] = O\left(\frac{n \log(nT)}{\Delta_{\min}^2}\right)$$
本論文は、情報理論的な下界を導出することにより、この境界が近最適 (near-optimal) であることを証明している。下界は、いかなるアルゴリズムも $\Omega(n \log(T)/\Delta_{\min}^2)$ の識別時間を負う必要があることを示している。提案された二段階アプローチは、対数因子を除いてこの下界と一致しており、「ナビゲーションのコスト」が問題の統計的な困難さを（識別要求を超えて）根本的に増大させないことを示している。

シミュレーション

理論的な知見は以下の通り検証されている：

1. 制御実験: i.i.d. ER および Edge-Markovian グラフを用いたシミュレーションにより、平均リグレットがゼロに収束すること、およびナビゲーション時間がエッジ確率 $p$ に対して反比例すること（すなわち $O(1/p)$）が確認されている。
2. ロボット災害対応シナリオ: 災害地における通信リレーサイトを探索する地上車両のシミュレーション。車両は局所的なセンシング（グローバルマップなし）で動作し、動的に変化する街路ネットワーク（Edge-Markovian）をナビゲートする。結果は、アルゴリズムが最適な場所を特定し、そこに収束することを示しており、FMAB モデルの実用的な適用可能性を検証している。

4. 意義と貢献

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

• 斬新なフレームワーク: 本論文は、局所移動制約 (local-move constraints)（ナビゲーション）を不確実性下での逐次的決定論と明示的に結合させた最初のモデルとして、FMAB フレームワークを導入している。これは、可用性がエージェントの行動とは無関係である、あるいはグローバルに既知であると仮定する既存の「Sleeping」または「Volatile」バンディットの文献におけるギャップに対処している。
• 統一された分析: 進化するランダムグラフ上での学習に関する、i.i.d. および Markovian ダイナミクスの両方を扱う統一されたリグレット分析を提供している。
• アルゴリズムの堅牢性: 提案された Lazy Random Walk 戦略は、多様な接続レジーム（均質、不均質、および時間相関あり）において堅牢であることが示されている。
• 基本的限界: 一致する下界を確立することで、本研究は局所移動制約下での学習に伴う本質的なコストを特徴付けており、ナビゲーションの物理的なオーバーヘッドが、学習の根本的な統計的レート（対数因子を除いて）を低下させないことを証明している。
• 実用的な関連性: 本研究は、理論的なオンライン学習と物理的な制約を橋渡しし、グローバルマップを持たず、オプション間をテレポートできないエージェントが運用されるロボティクス、災害対応、およびネットワークシステムへの厳密な基礎を提供する。

著者らは、高確率分析は特定のグラフパラメータに依存するものの、最終的な期待リグレットは基本的な問題パラメータ ($n, T, \Delta_{\min}$) のみに依存することを示唆しており、環境の構造的制約が提案された探索戦略によって効果的に管理されていると結論付けている。