解説
「もし最初から正解を知っていたら得られた利益」と「実際の利益」の差（後悔）を、試行錯誤の中で最小にしようとする従来のアプローチ。
さらに詳しく解説
リグレット最小化（Regret Minimization）は、「最良の選択肢を後から振り返ったときの差分（後悔の量）」を最小にすることを目指す意思決定の枠組みです。多腕バンディット・ゲーム理論・オンライン学習などで用いられ、AIにおける戦略学習の重要な理論基盤になっています。
リグレットの定義
リグレット = 最善の選択を取り続けた場合の累積報酬 − 実際の累積報酬例えば、3種類の広告を試したとき、最終的に最良の広告だけを最初から流していたら得られた報酬と、実際の試行錯誤で得た報酬の差がリグレットです。
探索と活用のバランス
リグレット最小化アルゴリズムは、多腕バンディットで出てくる「探索（Exploration）vs 活用（Exploitation）」のジレンマを理論的に扱う枠組みでもあります。
- 探索しすぎ → 既に分かっている良い選択肢を活用しないことでリグレット増
- 活用しすぎ → より良い選択肢を見逃すことでリグレット増
代表的なアルゴリズム
| アルゴリズム | 特徴 |
|---|---|
| ε-greedy | シンプル、リグレット保証は緩い |
| UCB | 信頼区間ベース、対数オーダーのリグレット保証 |
| EXP3 | 敵対的環境でも保証あり |
| CFR（Counterfactual Regret Minimization） | ゲーム理論で利用、ポーカーAIで有名 |
| Hedge / Multiplicative Weights | オンライン学習の基本手法 |
ゲーム理論での応用：CFR
ポーカーなどの不完全情報ゲームでは、CFR（反実仮想リグレット最小化）がブレークスルーをもたらしました。
- Libratus / Pluribus：プロを破ったポーカーAIはCFR系
- **AlphaStar / OpenAI Five**：複雑なゲームでもリグレット最小化的発想を活用
AIでの応用領域
- **ABテスト最適化**：従来手法より早く勝者を決定
- 広告配信：複数広告のクリック率を学習しつつ最良を表示
- 推薦システム：新規コンテンツの探索を理論的に保証
- **ハイパーパラメータ探索**：効率的な探索アルゴリズム
- 対戦型ゲームAI：均衡戦略の発見
リグレット保証の意味
「リグレットがT回の試行に対して O(√T) で抑えられる」といった保証は、長期的に最良戦略との差が相対的に縮まることを意味します。理論的に良い性質を持つアルゴリズムは、実装上も安定して機能することが多くあります。
実務での扱い
直接「リグレット最小化アルゴリズム」を実装することは少ないものの、ABテストツール・推薦システム・強化学習ライブラリの中核に組み込まれています。理論を理解しておくと、各ツールがなぜそのような挙動をするのか納得しやすくなります。
リグレット最小化は「失敗から学ぶ」を数学的に定式化した枠組みで、現代の意思決定AIの基礎理論として広く活用されています。