本記事は arXiv:2604.25269 の解説記事です。
論文概要（Abstract）
Tsuchiya, Ito, Honda（2026）は、行動の利用可能性が確率的に変動するオンライン組合せ最適化（sleeping設定）においてCAT（Combine-and-Transform）アルゴリズムを提案した。CATは利用可能性で重み付けした損失変換を核とし、full-information設定のregretをNeu & Valko（NeurIPS 2014）の $O(\sqrt{K^2 T / p_{\min}})$ から $O(\sqrt{KT / p_{\min}})$ に改善する。さらにmatching lower boundにより、この上界がnear-optimalであることを証明している。
この記事は Zenn記事: Sleeping Banditの組合せ最適化：CAT手法によるregret改善の理論と実装 の深掘りです。
情報源
- arXiv ID: 2604.25269
- URL: https://arxiv.org/abs/2604.25269
- 著者: Taira Tsuchiya, Shinji Ito, Junya Honda
- 発表年: 2026
- 分野: cs.LG, stat.ML
背景と動機（Background & Motivation）
オンライン組合せ最適化では、学習者がスパニング木・マッチング・経路などの組合せ構造から行動を選択し、敵対的に決まる損失を最小化する。標準設定では行動集合が固定されるが、実世界では行動の利用可能性が変動する場面が多い。推薦システムにおける商品の在庫切れ、ネットワークルーティングにおけるリンク障害などがその例である。
Neu & Valko（NeurIPS 2014）はこの問題に対しFPL（Follow-the-Perturbed-Leader）ベースのアルゴリズムを初めて提案したが、full-information設定で $O(\sqrt{K^2 T / p_{\min}})$、bandit設定で $O(K^{3/2}\sqrt{T / p_{\min}})$ というregret上界にとどまっていた。$K$（基底行動数）への依存性が標準（non-sleeping）設定の下界より大きく、改善の余地が理論的に示唆されていた。
主要な貢献（Key Contributions）
- 貢献1: CATアルゴリズムの提案。利用可能性確率 $p_i$ で除算する損失変換により、分散の $K$ 依存性を $K^2$ から $K$ に削減
- 貢献2: full-information regretを $O(\sqrt{KT / p_{\min}})$ に改善。Neu & Valkoの $O(\sqrt{K^2 T / p_{\min}})$ から $\sqrt{K}$ 倍の改善
- 貢献3: matching lower bound $\Omega(\sqrt{KT / p_{\min}})$ を構成し、full-information設定でのnear-optimalityを証明
- 貢献4: bandit設定で $O(\sqrt{K^3 T / p_{\min}})$ のregret上界を達成
技術的詳細（Technical Details）
問題設定
$K$ 個の基底行動（アーム）から構成される決定集合 $\mathcal{A} \subseteq {0,1}^K$ を考える。各ラウンド $t = 1, \ldots, T$ で以下が起こる。
- 環境が利用可能集合 $A_t$ を生成（各アーム $i$ は確率 $p_i$ で独立に利用可能）
- 学習者が $A_t$ を観測し行動 $\mathbf{a}_t \in A_t$ を選択
- 敵対的に決まる損失ベクトル $\boldsymbol{\ell}_t \in [0,1]^K$ に対し損失 $\langle \boldsymbol{\ell}_t, \mathbf{a}_t \rangle$ を被る
ここで $p_{\min} = \min_i p_i$ を最小利用可能確率とする。
CATの核心：利用可能性重み付け損失変換
CATの鍵は損失推定量の構成にある。従来手法（Neu & Valko）は importance-weighted estimator を使用していたが、その分散が $O(1/p_i^2)$ となり $K$ 項の合計で $O(K^2 T / p_{\min})$ のregretに帰結していた。
CATは以下の変換を用いる。
\[\tilde{\ell}_{t,i} = \frac{\ell_{t,i} \cdot \mathbf{1}[i \in A_t]}{p_i}\]ここで $\mathbf{1}[i \in A_t]$ はアーム $i$ がラウンド $t$ で利用可能かどうかの指示関数である。
この推定量の分散は以下のように抑えられる。
\[\mathbb{E}[(\tilde{\ell}_{t,i})^2] = \mathbb{E}\left[\frac{\ell_{t,i}^2 \cdot \mathbf{1}[i \in A_t]}{p_i^2}\right] = \frac{\ell_{t,i}^2}{p_i} \leq \frac{1}{p_i}\]従来手法では $\mathbb{E}[(\hat{\ell}_{t,i})^2] \leq 1/p_i^2$ であったのに対し、CATでは $1/p_i$ に改善されている。この改善がregret上界の $K$ 依存性を $K^2$ から $K$ に削減する根拠となる。
アルゴリズム：CAT（Full-Information版）
著者らが提案するCATアルゴリズム（論文 Section 3 Algorithm 1 より）の構造を以下に示す。
1
2
3
4
5
6
7
入力: 決定集合構造、学習率 η、摂動スケール γ
for t = 1, ..., T:
1. 利用可能集合 A_t を観測
2. 摂動 Z_t ~ Exp(γ)^K を生成
3. 変換損失を計算: ℓ̃_{t,i} = ℓ_{t,i} · 1[i ∈ A_t] / p_i
4. 行動選択: a_t = argmin_{a ∈ A_t} ⟨Σ_{s<t} ℓ̃_s + Z_t, a⟩
5. 損失 ℓ_{t,i} (i ∈ A_t) を観測
ステップ3の損失変換が従来のFPL-Sleepingとの本質的な違いである。$p_i$ で除算することで、累積変換損失が「実効的な」累積損失の不偏推定量となり、確率的利用可能性の影響を相殺する。
Bandit版の拡張
Semi-bandit設定では選択した行動の損失のみ観測できるため、追加の推定が必要になる。CATのbandit版では importance-weighted estimator を組み合わせる。
\[\hat{\ell}_{t,i} = \frac{\ell_{t,i} \cdot \mathbf{1}[i \in \mathbf{a}_t]}{p_i \cdot q_{t,i}}\]ここで $q_{t,i}$ はアーム $i$ のラウンド $t$ での周辺選択確率である。$p_i$ と $q_{t,i}$ の両方で除算する二重の importance weighting が特徴的である。
Regret解析の骨子
Theorem 1（Full-Information Regret）の証明概略（論文 Appendix A より）：
標準的なFPLのregret分解は以下の形をとる。
\[R_T \leq \sum_{t=1}^T \mathbb{E}[\langle \tilde{\boldsymbol{\ell}}_t, \mathbf{a}_t - \mathbf{a}^* \rangle] + \text{Perturbation Bias}\]鍵となるステップは累積分散の上界である。各アーム $i$ について、
\[\sum_{t=1}^T \text{Var}[\tilde{\ell}_{t,i}] \leq \frac{T}{p_i} \leq \frac{T}{p_{\min}}\]$K$ 個のアームの合計で累積分散は $O(KT / p_{\min})$ となる。著者らはmatrix stability arguments（論文 Proposition 4）を用いてこの分散上界をFPLのregretに結び付け、最終的に以下を得ている。
\[R_T \leq O\left(\sqrt{\frac{KT}{p_{\min}}}\right)\]学習率は $\eta = \sqrt{K / (T p_{\min})}$ と設定する。
下界の構成
Theorem 3（Lower Bound）: 任意のアルゴリズムに対し、full-information sleeping設定で以下を満たす問題インスタンスが存在する。
\[R_T \geq \Omega\left(\sqrt{\frac{KT}{p_{\min}}}\right)\]この下界は上界と一致し、CATのfull-information regretがnear-optimalであることを証明する。著者らはLe Cam法を用いた仮説検定ベースの構成を採用している。
実装のポイント（Implementation）
CATの実装における注意点を以下にまとめる。
利用可能性確率 $p_i$ の既知性: CATは $p_i$ が既知であることを前提とする。実用上 $p_i$ が未知の場合、標本平均 $\hat{p}i = \frac{1}{t} \sum{s=1}^t \mathbf{1}[i \in A_s]$ で推定する必要がある。ただし推定誤差がregretに与える影響は論文の分析範囲外であり、理論保証が変わる可能性がある。
組合せ最適化のオラクル: ステップ4の $\arg\min$ は組合せ構造に応じて効率的に計算可能である。スパニング木ならKruskal法（$O(K \log K)$）、最短経路ならDijkstra法（$O(K + V \log V)$）、マッチングならHungarian法（$O(V^3)$）を使う。
$p_{\min}$ が小さい場合の注意: $p_{\min} \to 0$ ではregretが発散する。著者らの実験でも、$p_{\min}$ が小さい環境での改善が顕著であると報告されている。
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
import numpy as np
class CATAlgorithm:
"""CAT (Combine-and-Transform) アルゴリズム (Full-Information版)
arXiv:2604.25269 Section 3, Algorithm 1 に基づく実装。
"""
def __init__(self, d: int, availability_probs: np.ndarray, eta: float):
self.d = d
self.p = availability_probs
self.eta = eta
self.cumulative_transformed_loss = np.zeros(d)
def select_action(
self, available_actions: list[np.ndarray],
) -> np.ndarray:
perturbation = np.random.exponential(scale=1.0, size=self.d)
scores = self.eta * self.cumulative_transformed_loss - perturbation
best_action = min(available_actions, key=lambda a: a @ scores)
return best_action
def update(
self, loss: np.ndarray, available: np.ndarray,
) -> None:
transformed = loss * available / self.p
self.cumulative_transformed_loss += transformed
実験結果（Results）
著者らは3つの実験設定でCATを評価している（論文 Section 5 より）。
| 実験設定 | 規模 | CAT | Neu & Valko (2014) | 改善 |
|---|---|---|---|---|
| Synthetic spanning tree | N=20, K=100 | 低regret | 中程度 | K依存性の改善が顕著 |
| OpenStreetMap shortest path | 実データ | 低regret | 高regret | 大規模グラフで差が拡大 |
| 推薦（在庫制約付き） | 実データ | 低regret | 中程度 | $p_{\min}$小で改善大 |
論文 Section 5 の実験結果によると、$p_{\min}$ が小さい環境（利用不可が頻繁に発生する環境）でCATの優位性が際立つ。著者らは「CATの利用可能性重み付け損失変換が、高い利用不可率の環境で自動的に適応する」と述べている。
bandit設定の実験では、CATは marginal selection probability $q_{t,i}$ のリサンプリング推定にモンテカルロ法を用いており、リサンプリング回数 $M$ の増加に伴いregretが安定化する傾向が報告されている。
実運用への応用（Practical Applications）
CATアルゴリズムが直接適用できる実務シナリオとして、以下が論文で言及されている。
- 推薦システム: ECサイトで商品の在庫状況が確率的に変動する場合、CATは在庫確率で損失を正規化し、利用可能な商品組合せの最適推薦を効率的に学習する
- ネットワークルーティング: リンク障害が確率的に発生するネットワークにおいて、利用可能な経路から最短経路を逐次学習する。OpenStreetMapデータでの実験がこの応用を実証している
- 広告配信: 広告枠の在庫が確率的に変動する環境でのポートフォリオ最適化
いずれの応用でも、$p_i$ の推定精度がアルゴリズム性能に直結するため、十分なウォームアップ期間を設けることが実用上の課題となる。
関連研究（Related Work）
- Neu & Valko (NeurIPS 2014): sleeping組合せ最適化にFPLを初適用。CATの直接の改善対象であり、full-informationで $O(\sqrt{K^2 T / p_{\min}})$ を達成（arXiv:1404.7530）
- Tsuchiya & Ito (2025): FPLにTsallis摂動を導入しBest-of-Both-Worlds保証を達成。CATの理論基盤を提供（arXiv:2504.07307）
- Pacchiano et al. (2024): per-action regretフレームワークを提案し、各行動の利用可能ラウンドに基づく個別regret保証を導出（arXiv:2403.01315）
- Kleinberg et al. (2010): sleeping expert問題のregret boundを確立した基礎研究
まとめと今後の展望
CATアルゴリズムは、sleeping組合せ最適化のfull-information regretを $O(\sqrt{KT / p_{\min}})$ に改善し、matching lower boundでnear-optimalityを証明した。損失変換 $\tilde{\ell}{t,i} = \ell{t,i} \cdot \mathbf{1}[i \in A_t] / p_i$ という単純な操作が、分散を $1/p_i^2$ から $1/p_i$ に削減する点が理論的に重要である。
今後の研究方向として、著者らはbandit設定のtight lower bound（現在は未解決）と、adversarial availability（利用可能性も敵対的に決まる設定）への拡張を挙げている。
参考文献
- arXiv: https://arxiv.org/abs/2604.25269
- Related Zenn article: https://zenn.dev/0h_n0/articles/7602fff38b7909
- Neu & Valko (NeurIPS 2014): https://arxiv.org/abs/1404.7530
- Tsuchiya & Ito (2025): https://arxiv.org/abs/2504.07307