論文解説: Follow-the-Perturbed-LeaderによるBest-of-Both-Worlds保証 — Tsallis摂動の理論と組合せバンディットへの応用

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

論文概要（Abstract）

Tsuchiya & Ito（2025）は、Follow-the-Perturbed-Leader（FPL）アルゴリズムにTsallis型摂動分布を導入することで、オンライン組合せ最適化においてBest-of-Both-Worlds（BoBW）保証を達成した。FPLは組合せ構造に対して計算効率が高いが、従来は敵対的設定のregret解析のみが知られていた。著者らはFPLとFTRL（Follow-the-Regularized-Leader）のTsallis entropy正則化器との等価性を示す結合補題を確立し、FPLが確率的設定で $O(K \log T / \Delta_{\min})$、敵対的設定で $O(\sqrt{KT})$ の両方を単一アルゴリズムで達成することを証明した。

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

情報源

arXiv ID: 2504.07307
URL: https://arxiv.org/abs/2504.07307
著者: Taira Tsuchiya, Shinji Ito
発表年: 2025
分野: cs.LG, stat.ML

背景と動機（Background & Motivation）

FPLは組合せ最適化の実用的アルゴリズムとして広く用いられている。各ラウンドで累積損失にランダム摂動を加え、摂動付き損失を最小化する行動を選択する。スパニング木・マッチング・最短経路などの組合せ構造に対し、$\arg\min$ を多項式時間のアルゴリズム（Kruskal法、Hungarian法、Dijkstra法）で計算できるため、指数的な行動数を持つ問題でも効率的に動作する。

一方、EXP3やFTRLのような確率的行動選択を行うアルゴリズムは行動空間全体にわたる確率分布の維持が必要で、組合せ構造に対する計算コストが高い。Best-of-Both-Worlds（BoBW）の概念はBubeck & Slivkins（COLT 2012）が導入したもので、確率的環境（損失がi.i.d.）と敵対的環境（損失が任意）の両方でnear-optimal regretを同時に達成するアルゴリズムを求める。FTRLではZimmert & Seldin（JMLR 2021）がTsallis entropy正則化でBoBWを実現したが、FPLでの達成は未解決であった。

主要な貢献（Key Contributions）

貢献1: FPLにTsallis型摂動（密度 $\propto \exp(-\alpha \cdot x^{1/2})$）を導入したFPL-BoBWアルゴリズムの提案
貢献2: FPL-FTRL結合補題（Lemma 1）の確立。Tsallis摂動下でFPLの行動選択分布がFTRLのTsallis entropy正則化と正確に一致することを証明
貢献3: 敵対的regret $O(\sqrt{KT})$ と確率的regret $O(K \log T / \Delta_{\min})$ の同時達成（単一パラメータ設定）
貢献4: sleeping設定への拡張。full-information $O(\sqrt{KT / p_{\min}})$、bandit $O(\sqrt{K^3 T / p_{\min}})$

技術的詳細（Technical Details）

FPL-BoBWアルゴリズム

著者らが提案するアルゴリズムの中心的な変更点は摂動分布の選択にある。従来のFPLはGaussian摂動やGumbel摂動を使用していたが、FPL-BoBWではTsallis型摂動を採用する。

アルゴリズム FPL-BoBW（論文 Section 2 より）:

入力として行動空間 $\mathcal{A} \subseteq {0,1}^K$ とパラメータ $\alpha, \beta$ を受け取る。

各ラウンド $t = 1, \ldots, T$ で以下を実行する。

摂動 $Z_t$ を生成。各成分 $Z_{t,i}$ は密度 $f(x) \propto \exp(-\alpha \cdot x^{1/2})$ ($x \geq 0$) から独立にサンプル
行動選択: $\mathbf{a}t = \arg\min{\mathbf{a} \in \mathcal{A}} \langle \mathbf{L}_{t-1} + \mathbf{Z}_t, \mathbf{a} \rangle$
フィードバック観測（full-information: $\boldsymbol{\ell}_t$ 全体、bandit: $\boldsymbol{\ell}_t(\mathbf{a}_t)$ のみ）

ここで $\mathbf{L}{t-1} = \sum{s<t} \boldsymbol{\ell}_s$ は累積損失ベクトルである。

Tsallis摂動の背景

Tsallis摂動は $1/2$-Tsallis entropy $H_{1/2}(\mathbf{p}) = 2\sum_i (p_i - p_i^{1/2})$ の正則化と対応する。Tsallis-INFアルゴリズム（Zimmert & Seldin, 2021）はFTRLにこの正則化を用いてBoBWを達成したが、FPLとの関係は不明であった。

摂動密度 $f(x) \propto \exp(-\alpha \cdot x^{1/2})$ は以下の性質を持つ。

\[\mathbb{E}[Z_{t,i}] = \frac{2}{\alpha^2}, \qquad \text{Var}[Z_{t,i}] = \frac{8}{\alpha^4}\]

Gaussian摂動（$\mathbb{E}[Z^2] \propto 1/\alpha^2$）と比較して、Tsallis摂動はテール構造が異なり、確率的設定での適応性を実現する。

FPL-FTRL結合補題

本論文の最も重要な技術的貢献はFPL-FTRL Coupling Lemma（論文 Lemma 1）である。

Lemma 1: 任意の累積損失ベクトル $\mathbf{L}$ に対し、Tsallis摂動によるFPLの行動選択分布

\[\Pr[\mathbf{a}_t = \mathbf{a}] = \Pr\left[\mathbf{a} = \arg\min_{\mathbf{a}' \in \mathcal{A}} \langle \mathbf{L} + \mathbf{Z}, \mathbf{a}' \rangle\right]\]

は、FTRLの $1/2$-Tsallis entropy正則化による分布

\[\mathbf{p}^{\text{FTRL}} = \arg\min_{\mathbf{p} \in \Delta(\mathcal{A})} \left\{ \langle \mathbf{L}, \mathbf{p} \rangle + \frac{1}{2\alpha^2} H_{1/2}(\mathbf{p}) \right\}\]

と正確に一致する。

この結合によりFTRLのBoBW理論をFPLに直接インポートできる。具体的には、FTRLにおけるTsallis entropyのself-bounding property（確率的設定で対数的regretを導く性質）がFPLにも成立する。

Regret上界

Theorem 1（Adversarial Regret）: $\alpha = \sqrt{K/T}$ で

\[R_T^{\text{adv}} \leq O(\sqrt{KT})\]

Theorem 2（Stochastic Regret）: gap-adaptive設定で

\[R_T^{\text{sto}} \leq O\left(\frac{K \log T}{\Delta_{\min}}\right)\]

ここで $\Delta_{\min}$ は最適行動と次善行動の損失差の最小値である。

両方の上界は単一のパラメータ選択（gap-adaptiveバージョン）で同時に達成される。環境が確率的か敵対的かを事前に知る必要がない。

Sleeping設定への拡張

Theorem 3（Sleeping Extension）: 各アーム $i$ の利用可能確率が $p_i \geq p_{\min}$ である確率的sleeping設定で、

\[R_T^{\text{sleep, adv}} \leq O\left(\sqrt{\frac{KT}{p_{\min}}}\right)\] \[R_T^{\text{sleep, sto}} \leq O\left(\frac{K \log T}{p_{\min} \cdot \Delta_{\min}}\right)\]

sleeping拡張は以下の2つの変更で実現される。

$\arg\min$ を現在の利用可能集合 $A_t$ に制限する
学習率を $1/p_{\min}$ でスケーリングする

著者らはstability解析（Proposition 5）で、利用可能集合が変動する場合の摂動の「互換性」を保証している。

実装のポイント（Implementation）

Tsallis摂動のサンプリング: 密度 $f(x) \propto \exp(-\alpha \cdot x^{1/2})$ からの逆CDF法が利用可能である。CDF $F(x) = 1 - \exp(-\alpha \sqrt{x}) \cdot (1 + \alpha \sqrt{x})$ から逆関数を数値的に求める。

Gap-adaptiveパラメータ設定: $\Delta_{\min}$ は事前に不明のため、doubling trick（$\Delta$ の推定値を段階的に更新）またはself-tuning版が必要となる。論文ではdoubling trickを推奨している。

組合せ構造の活用: FPLの $\arg\min$ は組合せ構造に応じた効率的アルゴリズムで計算する。$m$-set semi-bandit（$d$ 個のアームから $m$ 個を選択）では、$\arg\min$ はスコアの昇順で上位 $m$ 個を選ぶだけで $O(d \log d)$ で計算可能。

  
import numpy as np
from scipy.optimize import brentq

def sample_tsallis_perturbation(alpha: float, size: int) -> np.ndarray:
    """Tsallis型摂動を逆CDF法でサンプリングする

    密度: f(x) ∝ exp(-α·√x), x ≥ 0
    """
    u = np.random.uniform(0, 1, size=size)
    samples = np.zeros(size)
    for i in range(size):
        def cdf_minus_u(x: float) -> float:
            sx = np.sqrt(max(x, 0))
            return 1.0 - np.exp(-alpha * sx) * (1.0 + alpha * sx) - u[i]
        samples[i] = brentq(cdf_minus_u, 0, 100 / alpha**2)
    return samples


class FPLBoBW:
    """FPL-BoBW: Best-of-Both-Worlds保証付きFPL

    arXiv:2504.07307 Section 2 に基づく。
    """

    def __init__(self, d: int, alpha: float):
        self.d = d
        self.alpha = alpha
        self.cumulative_loss = np.zeros(d)

    def select_action(
        self, available_actions: list[np.ndarray],
    ) -> np.ndarray:
        z = sample_tsallis_perturbation(self.alpha, self.d)
        scores = self.cumulative_loss + z
        return min(available_actions, key=lambda a: a @ scores)

    def update(self, loss: np.ndarray) -> None:
        self.cumulative_loss += loss

実験結果（Results）

著者らはspanning treeインスタンスとshortest pathインスタンスで実験を行っている（論文 Section 5 より）。

設定	FPL-BoBW	標準FPL (Gaussian)	FTRL (log-barrier)
確率的	$O(\log T)$ に収束	$O(\sqrt{T})$ のまま	$O(\log T)$ に収束
敵対的	$O(\sqrt{T})$	$O(\sqrt{T})$	$O(\sqrt{T})$

著者らの実験によると、FPL-BoBWは確率的環境で標準FPLを大幅に上回り、FTRLと同等の対数的regretを達成する。敵対的環境では全手法が $O(\sqrt{T})$ で同程度の性能を示す。FPL-BoBWの利点は、FTRLの分布維持コストなしに両方の保証を得られる計算効率にある。

実運用への応用（Practical Applications）

FPL-BoBWの実用的な価値は「環境が確率的か敵対的かを事前に判断する必要がない」点にある。

A/Bテストの自動最適化: ウェブサービスのA/Bテストで、通常は確率的だが競合他社の行動により一時的に敵対的になる環境に適応可能
動的価格設定: 需要が定常的な期間と、セール・イベントで非定常な期間が混在する環境での価格最適化
ポートフォリオ選択: 市場が効率的（確率的）な通常時と、危機時（敵対的）の両方に対応する投資戦略

sleeping拡張により、アセットの流動性不足（一時的に取引不可）にも対応できる。

まとめと今後の展望

FPL-BoBWは、Tsallis型摂動とFPL-FTRL結合補題により、計算効率の高いFPLでBoBW保証を達成した。sleeping設定への拡張も自然に行え、CAT（arXiv:2604.25269）の理論基盤を提供している。著者らは、確率的bound中の対数因子の除去可能性をopen questionとして挙げている。

参考文献

arXiv: https://arxiv.org/abs/2504.07307
Related Zenn article: https://zenn.dev/0h_n0/articles/7602fff38b7909
Zimmert & Seldin (JMLR 2021): Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits
Bubeck & Slivkins (COLT 2012): The Best of Both Worlds: Stochastic and Adversarial Bandits

📄 論文解説: Follow-the-Perturbed-LeaderによるBest-of-Both-Worlds保証 — Tsallis摂動の理論と組合せバンディットへの応用

論文概要（Abstract）

情報源

背景と動機（Background & Motivation）

主要な貢献（Key Contributions）

技術的詳細（Technical Details）

FPL-BoBWアルゴリズム

Tsallis摂動の背景

FPL-FTRL結合補題

Regret上界

Sleeping設定への拡張

実装のポイント（Implementation）

実験結果（Results）

実運用への応用（Practical Applications）

関連研究（Related Work）

まとめと今後の展望

参考文献

📄 論文解説: Follow-the-Perturbed-LeaderによるBest-of-Both-Worlds保証 — Tsallis摂動の理論と組合せバンディットへの応用

論文概要（Abstract）

情報源

背景と動機（Background & Motivation）

主要な貢献（Key Contributions）

技術的詳細（Technical Details）

FPL-BoBWアルゴリズム

Tsallis摂動の背景

FPL-FTRL結合補題

Regret上界

Sleeping設定への拡張

実装のポイント（Implementation）

実験結果（Results）

実運用への応用（Practical Applications）

関連研究（Related Work）

まとめと今後の展望

参考文献

関連記事

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

📄 論文解説: Online Combinatorial Optimization with Sleeping Arms — CATアルゴリズムによるregret改善

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