本記事は arXiv:2603.19700 の解説記事です。
論文概要（Abstract）
Saha & Shekhar（2026）は、competing bandits（dueling bandits）モデルをsleeping設定に拡張した「Sleeping Competing Bandits」を提案した。標準のcompeting banditsでは学習者がペアのアームを選択し比較結果（どちらが優れているか）を観測するが、本論文のsleeping拡張では一部のアームが各ラウンドで利用不可になる。著者らは確率的利用可能性の下でSCB-UCBアルゴリズムにより $O(K^2 \log T / (\Delta_{\min} \cdot p_{\min}))$ のregretを、敵対的利用可能性の下でSCB-EXPにより $O(K\sqrt{T / p_{\min}})$ のregretを達成した。さらに敵対的設定でのmatching lower bound $\Omega(K\sqrt{T / p_{\min}})$ を証明している。
この記事は Zenn記事: Sleeping Banditの組合せ最適化：CAT手法によるregret改善の理論と実装 の深掘りです。
情報源
- arXiv ID: 2603.19700
- URL: https://arxiv.org/abs/2603.19700
- 著者: Aadirupa Saha, Shubhanshu Shekhar
- 発表年: 2026
- 分野: cs.LG, stat.ML
背景と動機（Background & Motivation）
Competing bandits（dueling bandits）は、数値的な報酬ではなくペア比較の結果のみが得られるバンディット問題のバリアントである。人間のフィードバックからの学習（RLHF: Reinforcement Learning from Human Feedback）やA/Bテスト、情報検索のランキング学習などで実務的に重要な設定である。
しかし、標準のcompeting banditsでは全アームが常に利用可能であることを仮定している。実世界では以下のような利用不可が発生する。
| 応用 | アームの例 | 利用不可の原因 |
|---|---|---|
| 推薦比較 | 比較対象の商品 | 在庫切れ |
| 臨床試験 | 治療選択肢 | 薬剤の供給不足 |
| ハイパーパラメータ最適化 | 設定候補 | 計算リソース制約 |
| オンライン広告 | 広告クリエイティブ | 予算消化・掲載期間終了 |
Saha & Shekharの動機は、比較フィードバック型のバンディット問題にsleeping設定を導入し、利用可能性変動下でのregret理論を確立することにある。
主要な貢献（Key Contributions）
- 貢献1: Sleeping Competing Banditsの問題定式化。比較フィードバック + sleeping設定の組合せを初めて形式的に研究
- 貢献2: SCB-UCBアルゴリズムの提案。確率的利用可能性の下で $O(K^2 \log T / (\Delta_{\min} \cdot p_{\min}))$ のCondorcet regret
- 貢献3: SCB-EXPアルゴリズムの提案。敵対的利用可能性の下で $O(K\sqrt{T / p_{\min}})$ のCondorcet regret
- 貢献4: 敵対的設定の下界 $\Omega(K\sqrt{T / p_{\min}})$。SCB-EXPのnear-optimality証明
技術的詳細（Technical Details）
問題設定
$K$ 個のアームと未知の選好行列 $\mathbf{M} \in [0,1]^{K \times K}$ を考える。$M_{ij} = \Pr[\text{アーム } i \text{ がアーム } j \text{ に勝つ}]$ と定義する。
各ラウンド $t = 1, \ldots, T$ で以下が起こる。
- 利用可能集合 $A_t \subseteq [K]$ が環境により決定される
- 学習者がペア $(i_t, j_t)$ を選択（$i_t, j_t \in A_t$）
- 比較結果 $X_t \sim \text{Bernoulli}(M_{i_t, j_t})$ を観測
利用可能性は2つの設定で分析される。
- 確率的: 各アーム $i$ は確率 $p_i$ で独立に利用可能（$p_{\min} = \min_i p_i$）
- 敵対的: 利用可能集合 $A_t$ は環境が任意に（学習者の過去の行動を見て）決定
Condorcet regret: Condorcet winner $i^$（全アームに対して過半数で勝つアーム、$M_{i^,j} > 1/2$ for all $j \neq i^*$）が存在すると仮定し、regretを以下で定義する。
\[R_T = \sum_{t=1}^T \left(M_{i^*, j_t} + M_{i^*, i_t} - 1\right)\]これはCondorcet winnerに対する余剰損失の合計であり、最適ペア $(i^, i^)$ を選んでいた場合との差を測定する。
SCB-UCBアルゴリズム（確率的利用可能性）
SCB-UCBは各ペア $(i,j)$ に対してUCB推定値を維持し、利用可能なアーム中から最も有望なペアを選択する。
\[U_{t,ij} = \hat{M}_{t,ij} + \sqrt{\frac{\ln t}{2 n_{t,ij}}}\]ここで $\hat{M}{t,ij}$ はペア $(i,j)$ の選好確率の標本平均、$n{t,ij}$ は両アームが利用可能で実際にこのペアが選択された回数である。
選択規則（論文 Section 3.1 より）:
- 利用可能アームの中から、UCB推定のCondorcet scoreが最大のアームを「チャンピオン」$c_t$ として選択
- チャンピオンと比較するための「チャレンジャー」$r_t$ を利用可能アームからランダムに選択
- ペア $(c_t, r_t)$ を選択し比較結果を観測
Condorcet score $S_t(i) = \sum_{j \in A_t \setminus {i}} U_{t,ij}$ は、アーム $i$ が利用可能な全アームにどれだけ勝ちそうかの指標である。
SCB-EXPアルゴリズム（敵対的利用可能性）
敵対的設定ではUCBベースの楽観的探索が使えないため、EXP3型のweight-based探索を用いる。
著者らのSCB-EXP（論文 Section 3.2 より）の設計は以下のとおりである。
各ペア $(i,j)$ に対して重み $w_{t,ij}$ を維持する。
\[w_{t+1,ij} = w_{t,ij} \cdot \exp\left(-\eta \cdot \frac{X_t \cdot \mathbf{1}[(i_t, j_t) = (i,j)]}{q_{t,ij}}\right)\]ここで $q_{t,ij}$ はペア $(i,j)$ の選択確率であり、利用可能ペア $A_t \times A_t$ 上の重み正規化で決定される。$X_t$ は比較結果（0 or 1）である。
Regret上界
Theorem 1（確率的利用可能性）: SCB-UCBは
\[\mathbb{E}[R_T] \leq O\left(\frac{K^2 \log T}{\Delta_{\min} \cdot p_{\min}}\right)\]ここで $\Delta_{\min} = \min_{j \neq i^} (M_{i^,j} - 1/2)$ は最小選好ギャップである。
$p_{\min}$ の依存性は、ペアの両方のアームが利用可能な確率が $p_i \cdot p_j \geq p_{\min}^2$ で下界されることから生じる。各ペアの観測機会が $1/p_{\min}^2$ 倍に希薄化されるが、Condorcet score推定に必要な比較回数が $O(K)$ ペアに渡るため、全体では $K^2 / p_{\min}$ のオーダーとなる。
Theorem 2（敵対的利用可能性）: SCB-EXPは
\[\mathbb{E}[R_T] \leq O\left(K\sqrt{\frac{T}{p_{\min}}}\right)\]Theorem 3（下界）: 敵対的利用可能性の下で、任意のアルゴリズムは
\[\mathbb{E}[R_T] \geq \Omega\left(K\sqrt{\frac{T}{p_{\min}}}\right)\]を満たす問題インスタンスが存在する。SCB-EXPの上界と一致し、near-optimalityが証明される。
Standard Sleeping Banditsとの関係
Sleeping Competing Banditsは、standard sleeping bandits（数値的報酬）とは本質的に異なる。
| 特徴 | Standard Sleeping Bandits | Sleeping Competing Bandits |
|---|---|---|
| フィードバック | 数値的損失 $\ell_t(a_t) \in [0,1]$ | 比較結果 $X_t \in {0,1}$ |
| 行動 | 単一アーム選択 | ペア選択 |
| 利用可能性の影響 | 各アーム独立 | ペアの両方が利用可能必要 |
| Regret比較対象 | 最適アーム | Condorcet winner |
| 組合せ構造 | ${0,1}^K$ の部分集合 | $K \times K$ のペア |
Zenn記事で解説されているNeu & Valkoの手法とは、フィードバック構造（数値 vs 比較）と行動構造（組合せ vs ペア）が異なる。しかし、sleeping設定での利用可能性確率による regret の劣化パターン（$1/p_{\min}$ への依存）は共通しており、sleeping問題に固有の普遍的現象であると考えられる。
実装のポイント（Implementation）
| ペア選択の計算量: SCB-UCBでは全 $O(K^2)$ ペアのUCB推定を維持するため、利用可能アーム数が大きい場合の計算コストに注意が必要である。各ラウンドのCondorcet score計算は $O(K | A_t | )$ となる。 |
敵対的利用可能性の検出: 実用上、利用可能性が確率的か敵対的かは事前に不明なことが多い。SCB-EXPは敵対的設定でも理論保証があるため、安全な選択となる。ただし確率的設定では $O(\sqrt{T})$ の regret がSCB-UCBの $O(\log T)$ より劣る。
選好行列の推定精度: $M_{ij}$ の推定にはペア $(i,j)$ が共に利用可能なラウンドのみを使用する。$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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
import numpy as np
class SCBUCB:
"""SCB-UCB: Sleeping Competing Bandits with UCB
arXiv:2603.19700 Section 3.1 に基づく実装。
"""
def __init__(self, k: int):
self.k = k
self.wins = np.zeros((k, k))
self.counts = np.zeros((k, k))
def select_pair(
self, available: np.ndarray, t: int,
) -> tuple[int, int]:
available_idx = np.where(available > 0)[0]
if len(available_idx) < 2:
raise ValueError("Need at least 2 available arms")
ucb = np.zeros((self.k, self.k))
for i in available_idx:
for j in available_idx:
if i == j:
continue
n = max(self.counts[i, j], 1)
ucb[i, j] = self.wins[i, j] / n + np.sqrt(np.log(t + 1) / (2 * n))
scores = np.zeros(self.k)
for i in available_idx:
scores[i] = sum(ucb[i, j] for j in available_idx if j != i)
champion = available_idx[np.argmax(scores[available_idx])]
challengers = [j for j in available_idx if j != champion]
challenger = np.random.choice(challengers)
return champion, challenger
def update(self, i: int, j: int, i_wins: bool) -> None:
self.counts[i, j] += 1
self.counts[j, i] += 1
if i_wins:
self.wins[i, j] += 1
else:
self.wins[j, i] += 1
実験結果（Results）
著者らは合成データとMovieLensデータで実験を行っている（論文 Section 5 より）。
| 実験設定 | SCB-UCB | SCB-EXP | Naive UCB |
|---|---|---|---|
| 合成 ($K=10$, $p_{\min}=0.7$) | $O(\log T)$ | $O(\sqrt{T})$ | linear growth |
| MovieLens ($K=20$, simulated sleeping) | 低regret | 中程度 | 高regret |
著者らの実験によると、Naive UCB（sleeping非対応の標準UCB）は利用不可アームを含むペアの推定が不正確になり、regretが線形に増大する。SCB-UCBは確率的利用可能性の下で対数的regretを達成するが、敵対的な摂動に対して脆弱である。SCB-EXPは設定を問わず安定したsublinear regretを示す。
実運用への応用（Practical Applications）
- RLHF（人間フィードバックからの強化学習）: LLMのアライメントで人間のペア比較フィードバックを用いる際、評価者の利用可能性が変動する場合にsleeping competing banditsが適用可能
- A/Bテスト: ウェブサービスのA/Bテストで、バリアント（機能実装）が一時的に障害で利用不可になる場合の統計的比較
- 推薦ランキング: 複数の推薦アルゴリズムのペア比較でアルゴリズム選択を最適化。一部アルゴリズムがリソース制約で一時停止する環境に対応
関連研究（Related Work）
- Yue & Joachims (ICML 2011): Beat the Mean Bandit。dueling banditsの基礎研究
- Zoghi et al. (ICML 2014): Relative Upper Confidence Bound。Condorcet winnerの効率的同定
- Komiyama et al. (COLT 2015): Regret lower bounds for dueling bandits
- Neu & Valko (NeurIPS 2014): sleeping組合せ最適化へのFPL適用（arXiv:1404.7530）
- Pacchiano et al. (2024): per-action regret。sleeping banditsの新しいregret指標（arXiv:2403.01315）
まとめと今後の展望
Saha & Shekhar（2026）はcompeting banditsにsleeping設定を導入し、比較フィードバック型のバンディット問題における利用可能性変動の影響を初めて体系的に分析した。敵対的設定でのmatching lower boundは、$1/p_{\min}$ への依存がsleeping問題に固有の普遍的コストであることを示唆している。
今後の研究方向として、著者らはBest-of-Both-Worlds保証（確率的・敵対的の同時最適化）のsleeping competing banditsへの拡張、およびContextual competing banditsとの統合を挙げている。
参考文献
- arXiv: https://arxiv.org/abs/2603.19700
- Related Zenn article: https://zenn.dev/0h_n0/articles/7602fff38b7909
- Yue & Joachims (ICML 2011): Beat the Mean Bandit
- Neu & Valko (NeurIPS 2014): https://arxiv.org/abs/1404.7530