Home 論文解説: Near-optimal Per-Action Regret Bounds for Sleeping Bandits — 行動ごとの最適regret保証
投稿
キャンセル

📄 論文解説: Near-optimal Per-Action Regret Bounds for Sleeping Bandits — 行動ごとの最適regret保証

投稿日 30/04/2026
投稿者 0h-n0
16 分読了時間

本記事は arXiv:2403.01315 の解説記事です。

論文概要（Abstract）

Pacchiano, Muthukumar, Bartlett（2024）は、sleeping bandit問題に新たなregret尺度「per-action regret」を導入した。従来のglobal regretが「常に利用可能な最適行動」との比較であるのに対し、per-action regretは各行動 $a$ の利用可能ラウンドのみで測定する個別的な指標である。著者らはAdaptively Sleeping EXP3（AS-EXP3）アルゴリズムを提案し、敵対的設定で各行動 $a$ に対して $O(\sqrt{T_a \ln K})$ のper-action regretを達成した。ここで $T_a$ は行動 $a$ が利用可能だったラウンド数である。さらにmatching lower boundを証明し、これらの上界がnear-optimalであることを示した。

この記事は Zenn記事: Sleeping Banditの組合せ最適化：CAT手法によるregret改善の理論と実装 の深掘りです。

情報源

背景と動機（Background & Motivation）

Sleeping bandit問題の標準的なregret定義には根本的な限界がある。global regretは「常に利用可能な最適行動」を比較対象とするが、すべての行動が時折利用不可になる場合、常に利用可能な行動が存在しないことがある。

具体的な例として、$K$ 個の行動が交互に利用可能になるケースを考える。行動1は奇数ラウンド、行動2は偶数ラウンドでのみ利用可能な場合、global regretの比較対象（常に利用可能な最適行動）が存在しないため、regretの定義自体が成り立たない。

per-action regretはこの問題を解決する。各行動 $a$ が利用可能だったラウンドでの余剰損失を個別に測定するため、利用可能性パターンに依存しない柔軟なregret尺度を提供する。

さらに、per-action regretの最小化はglobal regretの最小化を含意する（$a = a^*$ と設定すればよい）ため、より強い保証を与える。

主要な貢献（Key Contributions）

  • 貢献1: per-action regretフレームワークの形式的定義。各行動の利用可能ラウンドに基づく個別regret指標
  • 貢献2: AS-EXP3（Adaptively Sleeping EXP3）アルゴリズムの提案。各行動の利用可能ラウンドの累積損失のみで重みを更新
  • 貢献3: 敵対的per-action regret $O(\sqrt{T_a \ln K})$ の証明（Theorem 1）
  • 貢献4: 確率的per-action regret $O(\ln T / \Delta_a)$ の証明（Theorem 2）
  • 貢献5: 両設定でのmatching lower bound（Theorem 3）

技術的詳細（Technical Details）

Per-Action Regretの定義

$K$ 個のアーム（行動）と $T$ ラウンドのsleeping bandit問題を考える。ラウンド $t$ での利用可能集合を $A_t \subseteq [K]$ とし、学習者が選択したアームを $a_t \in A_t$、損失を $\ell_t(a_t)$ とする。

global regret（従来の定義）:

\[R_T = \mathbb{E}\left[\sum_{t=1}^T \ell_t(a_t)\right] - \min_{a^* \in \bigcap_t A_t} \mathbb{E}\left[\sum_{t=1}^T \ell_t(a^*)\right]\]

この定義は $\bigcap_t A_t = \emptyset$（常に利用可能なアームが存在しない）場合に意味をなさない。

per-action regret（本論文の定義）:

各アーム $a$ に対して

\[R_T^a = \mathbb{E}\left[\sum_{t: a \in A_t} \left(\ell_t(a_t) - \ell_t(a)\right)\right]\]
これはアーム $a$ が利用可能だったラウンドにおいて、学習者がアーム $a$ を選んでいた場合との損失差の合計である。$T_a ={t : a \in A_t}$ をアーム $a$ の利用可能ラウンド数とする。

per-action regretの利点は以下の通りである。

  1. 全アームが時折利用不可になるケースでも有効
  2. 各アームの品質を個別に評価できる
  3. 利用可能頻度に応じたadaptiveな保証を与える（$T_a$ が小さいアームほどregretが小さい）

AS-EXP3アルゴリズム

著者らが提案するAdaptively Sleeping EXP3（論文 Section 3 より）は、標準EXP3の重み更新を各アームの利用可能ラウンドに限定する。

アルゴリズム AS-EXP3:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

入力: K 個のアーム、パラメータ η
初期化: w_{0,i} = 1 (i = 1, ..., K)
for t = 1, ..., T:
  1. 利用可能集合 A_t を観測
  2. 利用可能アームの重みを正規化:
     π_t(i) = w_{t,i} / Σ_{j ∈ A_t} w_{t,j}  (i ∈ A_t)
  3. a_t ~ π_t を選択
  4. 損失 ℓ_t(a_t) を観測（banditフィードバック）
  5. 推定損失を計算:
     ℓ̂_t(a_t) = ℓ_t(a_t) / π_t(a_t)
     ℓ̂_t(i) = 0  (i ≠ a_t)
  6. 利用可能アームの重みのみ更新:
     w_{t+1,i} = w_{t,i} · exp(-η · ℓ̂_t(i))  (i ∈ A_t)
     w_{t+1,i} = w_{t,i}                       (i ∉ A_t)

ステップ6が核心である。利用不可のアーム $i \notin A_t$ の重みは更新されない。これにより各アームの重みはそのアームが利用可能だったラウンドの累積推定損失のみを反映する。

\[w_{t,i} = \exp\left(-\eta \sum_{s < t : i \in A_s} \hat{\ell}_s(i)\right)\]

従来のsleeping EXP3では利用不可アームの重みも（ゼロ損失として）更新するため、利用不可期間が長いアームの重みが相対的に上昇するバイアスが生じていた。AS-EXP3はこのバイアスを除去する。

Regret解析

Theorem 1（Adversarial Per-Action Regret）: AS-EXP3は $\eta = \sqrt{\ln K / T_a}$ で各アーム $a$ に対し

\[R_T^a \leq O(\sqrt{T_a \ln K})\]

を達成する。

証明の構造は標準EXP3のregret解析に類似するが、重要な違いはアーム $a$ が利用可能だったラウンドのみでの解析に限定される点である。

EXP3のregret分解は、ポテンシャル関数 $\Phi_t = \ln \sum_{i \in A_t} w_{t,i}$ を用いて

\[R_T^a \leq \frac{\ln K}{\eta} + \eta \sum_{t: a \in A_t} \mathbb{E}[\hat{\ell}_t(a_t)^2]\]

と上界される。第1項は初期化の影響（$\ln K / \eta$）、第2項は推定分散（$\eta$ に比例）である。

推定分散の上界は

\[\sum_{t: a \in A_t} \mathbb{E}[\hat{\ell}_t(a_t)^2] \leq \sum_{t: a \in A_t} \sum_{i \in A_t} \pi_t(i) \cdot \frac{\ell_t(i)^2}{\pi_t(i)^2} = \sum_{t: a \in A_t} |A_t| \leq K \cdot T_a\]

最適な $\eta = \sqrt{\ln K / (K T_a)}$ を代入し、$R_T^a \leq O(\sqrt{K T_a \ln K})$ を得る。著者らはより精密な解析で $K$ ファクタを除去し $O(\sqrt{T_a \ln K})$ を達成している。

Theorem 2（Stochastic Per-Action Regret）: 確率的設定（損失がi.i.d.）では、修正UCBアルゴリズムにより

\[\mathbb{E}[R_T^a] \leq O\left(\frac{\ln T}{\Delta_a}\right)\]

ここで $\Delta_a$ はアーム $a$ と利用可能な最適アームの期待損失差である。

Theorem 3（Lower Bound）: 任意のアルゴリズムに対し、敵対的設定で $\max_a R_T^a \geq \Omega(\sqrt{T_a \ln K})$、確率的設定で $\max_a \mathbb{E}[R_T^a] \geq \Omega(\ln T / \Delta_a)$ を満たす問題インスタンスが存在する。

実装のポイント（Implementation）

$T_a$ 未知の場合のパラメータ設定: $T_a$ は事前に不明であるため、$\eta$ の設定にdoubling trick（$T_a$ の推定を2倍ずつ増やしてリスタート）が必要である。著者らは、epoch $k$ で $\eta_k = \sqrt{\ln K / 2^k}$ と設定し、アーム $a$ の利用可能ラウンドが $2^k$ に達した時点でエポックを更新する方法を推奨している。

重みの数値安定性: $w_{t,i}$ は指数的に減少しうるため、対数空間で管理する（$\ln w_{t,i}$ を更新）ことで数値的安定性を確保する。

Per-action vs Global: 実用上、per-action regretの最小化がglobal regretの最小化より有用な場面は、利用可能性パターンが非一様なケースである。特定のアームが稀にしか利用可能にならない場合、global regretでは評価が困難だがper-action regretなら自然に評価できる。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

import numpy as np

class AdaptiveSleepingEXP3:
    """AS-EXP3: Adaptively Sleeping EXP3

    arXiv:2403.01315 Section 3 に基づく実装。
    """

    def __init__(self, k: int, eta: float):
        self.k = k
        self.eta = eta
        self.log_weights = np.zeros(k)

    def select_action(self, available: np.ndarray) -> int:
        available_idx = np.where(available > 0)[0]
        if len(available_idx) == 0:
            raise ValueError("No available arms")
        log_w = self.log_weights[available_idx]
        log_w -= log_w.max()
        w = np.exp(log_w)
        probs = w / w.sum()
        chosen = np.random.choice(len(available_idx), p=probs)
        self._last_probs = np.zeros(self.k)
        for i, idx in enumerate(available_idx):
            self._last_probs[idx] = probs[i]
        return available_idx[chosen]

    def update(
        self, chosen_arm: int, loss: float, available: np.ndarray,
    ) -> None:
        prob = self._last_probs[chosen_arm]
        estimated_loss = loss / max(prob, 1e-8)
        self.log_weights[chosen_arm] -= self.eta * estimated_loss

実験結果（Results）

論文には明示的な数値実験セクションはなく、理論的貢献が中心である。ただし、Section 6で以下の応用例を通じてper-action regretの実用性を議論している。

応用per-action regretの利点global regretの限界
Concept drift検出局所最適アームの個別評価可能常時最適アームが変動すると比較対象が不定
Federated learning各クライアントの個別性能保証全クライアント常時参加の仮定が非現実的
在庫制約付き推薦各商品の推薦品質を個別保証全商品が常時在庫ありの仮定が必要

著者らは、per-action regretが「局所的な最適性」を保証する点で、動的環境（concept driftやfederated learning）に適していると主張している。

実運用への応用（Practical Applications）

per-action regretの枠組みが有効な実務シナリオを整理する。

  • 推薦システム（在庫制約）: 各商品 $a$ について、在庫がある期間 $T_a$ での推薦品質を保証する。global regretでは全商品常時在庫ありの仮定が必要だが、per-action regretは在庫パターンに自然に適応する
  • Federated Learning: 各クライアント（アーム）がネットワーク障害等で一時的に参加できない場合、各クライアントの参加ラウンドにおけるモデル品質を個別保証する
  • 臨床試験: 各治療選択肢が供給制約で一時的に利用不可になる場合、各治療の利用可能期間での効果比較を可能にする

関連研究（Related Work）

  • Kanade et al. (AISTATS 2009): sleeping expert/bandit問題を定式化。global regretの枠組みを確立
  • Kleinberg et al. (ML Journal 2010): sleeping expertのregret boundを改善。non-stochastic利用可能性にも対応
  • Neu & Valko (NeurIPS 2014): sleeping設定の組合せ最適化にFPLを適用（arXiv:1404.7530）
  • Nguyen & Mehta (2022): sleeping expertのBest-of-Both-Worlds保証（arXiv:2203.01680）

まとめと今後の展望

Pacchiano et al.（2024）が提案したper-action regretは、sleeping bandit問題のregret評価に新たな視点を提供した。AS-EXP3は各アームの利用可能ラウンドのみで重みを更新するシンプルな変更で、near-optimalなper-action regretを達成する。per-action regretの最小化はglobal regretの最小化を含意するため、より厳密な性能保証を与える枠組みといえる。

今後の研究方向として、組合せ行動空間へのper-action regretの拡張が挙げられる。現状ではsingle-arm MABが主対象であり、スパニング木やマッチングなどの組合せ構造への直接的な拡張は未解決である。

参考文献

blog paper arxiv
sleeping-bandit per-action-regret online-learning bandit EXP3
この投稿は CC BY 4.0 でライセンスされています。
最近の更新
目次

論文解説: Online Combinatorial Optimization with Stochastic Decision Sets and Adversarial Losses — Sleeping組合せ最適化の原点

論文解説: Sleeping Competing Bandits — Dueling Banditのsleeping拡張とregret解析