バンディット問題の理論とアルゴリズム

後悔のない選択肢をあぶり出せ!
・さまざまな方策 (探索戦略) が、定量的かつ直感的に理解できる。
・最適腕識別や連続腕バンディットなどの発展的な内容も解説。
・モンテカルロ木探索やインターネット広告などのより具体的な状況への対応も紹介。

【機械学習プロフェッショナルシリーズ】
本シリーズでは、発展著しい機械学習技術の数学的な基礎理論、実用的なアルゴリズム、それらの活用法を、全 30 巻にわたって刊行する。
ビッグデータ時代を牽引している若手・中堅の現役研究者が、入門的な内容から最先端の研究成果までをわかりやすく解説。
これからデータサイエンス分野で研究を始めようとしている大学生・大学院生、および、機械学習技術を基礎科学や産業に応用しようとしている研究者・技術者に向けた注目のシリーズである。

第 5 期として、以下の 3 点を刊行!

バンディット問題の理論とアルゴリズム 本多 淳也/中村 篤祥・著
ウェブデータの機械学習 ダヌシカ ボレガラ/岡崎 直観/前原 貴憲・著
データ解析におけるプライバシー保護 佐久間 淳・著

第 6 期の刊行は 2016 年 12 月、第 7 期の刊行は 2017 年 4 月の予定。

【シリーズ編者】
杉山 将 東京大学大学院新領域創成科学研究科 教授
第 1 章 バンディット問題とは
第 2 章 確率的バンディット問題の基礎知識
第 3 章 確率的バンディット問題の方策
第 4 章 確率的バンディット問題のリグレット解析
第 5 章 敵対的バンディット問題
第 6 章 最適腕識別と A/B テスト
第 7 章 線形モデル上のバンディット問題
第 8 章 連続腕バンディットとベイズ最適化
第 9 章 バンディット問題の拡張
第 10 章 バンディット手法の応用

Web 広告の配信先、推薦する商品、試してみたい設計案。どれが一番よいか分からないまま試行を重ね、しかもその途中で得られる成果もできるだけ大きくしたい。この探索と活用の折り合いを数理の問題として扱うのがバンディット問題です。『バンディット問題の理論とアルゴリズム』 (本多淳也、中村篤祥 著、講談社、2016 年 8 月発行) は、講談社サイエンティフィクが編集する機械学習プロフェッショナルシリーズの 1 冊で、方策 (探索戦略) とリグレット解析の基礎理論から、最適腕識別、連続腕バンディット、モンテカルロ木探索やインターネット広告への応用までを 1 冊で通して解説した専門書です。版元の内容紹介は「後悔のない選択肢をあぶり出せ!」という一文で始まります。

全 10 章の構成、確率的バンディットから応用まで

第 1 章「バンディット問題とは」は問題の例、確率的バンディットと敵対的バンディットの区別、プレイヤー方策の評価法、歴史と関連分野を整理し、第 2 章「確率的バンディット問題の基礎知識」で中心極限定理による確率近似、裾確率の評価、大偏差原理を準備します。第 3 章「確率的バンディット問題の方策」は理論限界を示したうえで、貪欲法、UCB 方策と MED 方策、確率一致法とトンプソン抽出を順に取り上げ、第 4 章「確率的バンディット問題のリグレット解析」で UCB 方策とトンプソン抽出の性能を解析します。第 5 章「敵対的バンディット問題」は Hedge アルゴリズムから Exp3 方策、Exp3.P 方策、リグレット下界へ進みます。第 6 章「最適腕識別と A/B テスト」は標本複雑度と固定予算の設定、第 7 章「線形モデル上のバンディット問題」は文脈付きバンディットと LinUCB 方策、第 8 章「連続腕バンディットとベイズ最適化」は GP-UCB 方策や期待改善量方策を扱います。第 9 章「バンディット問題の拡張」で時間変化のある問題、比較バンディット、部分観測問題へ広げ、第 10 章「バンディット手法の応用」がモンテカルロ木探索、インターネット広告、推薦システムで締めくくります。巻末には付録 A「逆行列の更新」と付録 B「ベータ分布の裾確率」、参考文献、索引が付きます。

探索と活用のジレンマを測るリグレットという物差し

多腕バンディットは、報酬の分布が分からない複数の腕 (選択肢) から毎回 1 本を選び、得られた報酬だけを手がかりに次の選択を決める逐次意思決定の問題です。良さそうな腕ばかり引けば本当に良い腕を見逃し、満遍なく試せばそのぶん報酬を取りこぼします。最初から最良の腕を知っていた場合との差を積み上げたものがリグレットで、方策の良し悪しは、試行回数に対してリグレットがどの速さで増えるかで比べます。状態の遷移を持たない最も単純な 強化学習 の問題と見ることもでき、探索と活用の扱いを定理の形で確かめられる題材です。実務の側から見ると、固定の配分で一定期間試してから勝者を決める A/B テスト に対し、バンディット手法は試しながら配分を良い腕へ寄せていく考え方にあたります。本書は累積報酬の最大化と、最良の腕を少ない試行で見つけ出す最適腕識別を、目的の異なる問題として章を分けて整理しています。

確率の道具立てを前提に、理論を軸に読む専門書

版元の内容紹介は「方策やリグレット解析などの基礎理論を丁寧に解説」としており、楽天ブックスの書誌に載るシリーズの案内は、データサイエンス分野で研究を始めようとしている大学生 / 大学院生と、機械学習技術を基礎科学や産業に応用しようとしている研究者 / 技術者を読者に想定しています。数学の準備から固めたい場合は、機械学習に必要な数学の本 の選び方を先に確かめておくと読み進めやすくなります。目次は方策の定式化と解析を軸にしており、特定のライブラリの使い方を手早く知りたい目的であれば、実装を中心にした本のほうが近道です。

広告配信や推薦の配分ロジック、ハイパーパラメーター探索に使うベイズ最適化などで、なぜその方策を選ぶのかを保証の形で説明できるようになりたい人にとって、確率的、敵対的、線形、連続腕という主要な設定を同じ物差しで見渡せる本書は、論文へ進む前の足場として手元に置く価値のある 1 冊です。第 1 章で問題の全体像と本書の構成を確かめてから、目的に近い章へ進んでみてください。