Vol.26 No.3 (2011/05) 強化学習

私のブックマーク

強化学習

東京大学 総括プロジェクト機構 牧野 貴樹

はじめに

試行錯誤を通じて環境に適応する学習・制御の枠組みである強化学習について、内容は知らなくとも、耳にしたことのある方は多いと思います。ロボットの制御における行動選択の要として、また、神経科学における報酬・学習のシステムを理解するための鍵として、多くの研究がすすめられている分野です。
ここでは、強化学習の研究に関するページやリソースを紹介します。

強化学習入門

強化学習とは? http://sysplan.nams.kyushu-u.ac.jp/gen/edu/RL_intro.html

九州大学の木村 元先生のページです。web 上で強化学習を日本語で勉強したいなら、ここからはじめるといいでしょう。1999年の記事なので、多少古いですが、考え方を理解する入口としては十分な内容です。

Reinforcement Learning: An Introduction http://webdocs.cs.ualberta.ca/~sutton/book/the-book.html

Sutton と Barto の書いた、強化学習の定番の教科書が、HTML 形式で全文掲載されています。邦訳も出版されていますが（三上 貞芳・皆川 雅章 訳『強化学習』森北出版, 2000）、原文もとても読みやすいので、これから強化学習の研究に取り組むのであれば、最新の論文を読むための語彙力を身につけるためにも、原文で学ぶのがおすすめです。

Scholarpedia: Reinforcement Learning http://www.scholarpedia.org/article/Reinforcement_learning

2008年に書かれた、比較的新しいレビューです。強化学習の神経科学的側面と情報科学的側面の関係、現在の強化学習の直面している問題 (つまり、研究トピック) がわかりやすくまとめられています。

RL FAQ 日本語版 http://nao.s164.xrea.com/RL-FAQ-j.html

Sutton の 強化学習FAQ (http://webdocs.cs.ualberta.ca/~sutton/RL-FAQ.html)
の邦訳です。いきなり強化学習とバックプロパゲーションを組み合わせて研究するなど、典型的な初学者の陥る罠について書かれているので、目を通しておくとよいでしょう。

Myths of RL http://umichrl.pbworks.com/w/page/7597585/Myths-of-Reinforcement-Learning

「強化学習って結局～～なんじゃないの?」という様々な問いに対しての研究者側の答えが並べてあります。強化学習の研究をしながら、もやもやした疑問に悩まされている人は、このページを見るとすっきりするかもしれません。

POMDP for dummies http://www.cs.brown.edu/research/ai/pomdp/tutorial/index.html

POMDP (部分観測可能マルコフ決定過程) は、現在の状態を完全に観測できない (たとえば、迷路で自分の周囲しか見えない場合) 場合の事を指します。観測から現在の状態を推定しなければいけないので、学習の難易度は非常に高くなります。このページでは、POMDP に関する入門的内容に加え、いくつかの POMDP RL の解法を、数式を使わずに直観的に説明してくれています。

ツール・ライブラリ

RL Community
http://rl-community.org/wiki/Main_Page

強化学習の競技会のために作成ざた、エージェント・環境・実験プログラムの多言語インタフェース RL-Glue、そのインタフェースに沿って実装されたさまざまな学習アルゴリズム・環境のライブラリ RL-Library を入手できます。

Policy Gradient Toolbox
http://www.robot-learning.de/Research/PolicyGradientToolbox

Jan Peter による、方策勾配 (Policy Gradient) 法を利用した強化学習の MATLAB 用ツールボックスです。行動が離散ではない場合や、部分観測問題 (POMDP) など、古典的な価値関数ベースの手法が適用しにくい場合に有効とされる方策勾配法の研究を始めるには便利です。

Reinforcement Learning Toolbox http://www.igi.tugraz.at/ril-toolbox/general/overview.html

Neumann Gerhard による、C++ で記述された強化学習のツールボックスです。連続の状態空間が扱え、階層強化学習 (タスクがサブタスクに分解され、各々のサブタスクとサブタスクの並べ方の両方を強化学習で獲得する) やパッチ強化学習が利用できることが特徴です。

情報源

Reinforcement Learning Mailing List http://groups.google.com/group/rl-list?pli=1

強化学習のメーリングリストです (英語)。第一線の研究者が多く参加しているのでハイレベルですが、
学生からの質問などにも丁寧に返事が返ってきたりと、フランクな雰囲気で議論が交わされています。

Reinforcement Learning CFP http://mil.engr.utk.edu/nmil/cfps

強化学習に関連した学会等の Call for Paper を集めています。ICML、AAAI、IJCAI といった大きな学会から、もう少し小規模な学会までも網羅しているので、投稿の計画を立てるときに参考になります。

機械学習の「朱鷺の杜Wiki」http://ibisforest.org/index.php?強化学習

産総研の赤穂・神嶋らによる、機械学習に関する日本語のWikiサイトにも、強化学習に関する用語解説やリンクが掲載されています。ちょっとした調べ物をするときに便利です。

主な研究室

強化学習の理論そのものに取り組むのであれば、機械学習全般の理論という枠の中で強化学習を位置づけ、研究することが必要になるでしょう。以下は順不同で、機械学習の理論的研究をしている研究室の中で、比較的強化学習に関する研究がやりやすいと思えるところです。

強化学習を活用する研究としては、工学分野での応用を研究しているグループと、認知科学分野での応用を研究しているグループがありますが、オーバーラップがあり、明確に分けられません。ここでも、順不同で列挙します。

海外の研究室は数えだすときりがないので、主なものだけをリストアップします。これらは、さまざまなリソースへのリンクにもなっています。

応用

強化学習の応用って何があるの? と、強化学習の研究をしているとよく聞かれます。バックギャモンなどのゲーム、倒立・歩行などのロボット関係はすぐに思いつくのですが、
それ以外、となるとなかなか知らない人が多いのが現状ではないでしょうか。最近の応用を中心にいくつか紹介します。

ヘリコプター制御 http://heli.stanford.edu/

Stanford 大の Andrew Ng らのグループの研究成果です。人間のエキスパートの技を学習させるために、逆強化学習 (Inverse Reinforcement Learning) という技術 (報酬関数を未知として、人間のエキスパートの行動から報酬関数を推定する) を使っています。サイトに置いてあるアクロバット飛行のデモ動画は、一見の価値があります。

Windows ヘルプ文書理解 http://groups.csail.mit.edu/rbg/code/rl/

Windows のヘルプに出てくる操作手順の自然言語に対応する操作を学習します。従来であれば教師付き学習の枠組で研究されていた問題ですが、
「指示通りの操作が不可能」な場合に対して負の報酬を割り当て、どこまで指示に従った操作ができるかを強化学習によって学習することで、
教師データがない、あるいは少量しかない場合でも、精度の高い学習ができることを示しました。MIT の S.R.K.Branavan らによる本研究の論文は、ACL 2009 で Best paper award を受賞しています。

音声対話システム http://mi.eng.cam.ac.uk/research/dialogue/

Cambridge 大の Young らが開発した音声対話システムでは、ユーザーがシステムにしてほしい要求を隠れた状態と考え、ユーザーの発話内容を観測することで要求を明らかして対応する POMDP 問題と考えることで、最も適切な応答を学習すします。ノイズによって発話内容が正しく観測できない場合でも、従来のシステムに比べはるかに良い応答が実現できることが示されており、今後の実用化が期待されます。

構文解析 http://www.umiacs.umd.edu/~hal/SPIRL/10-07-acl-spirl.pdf

Maryland 大の Hal Daume III が ACL2010 tutorial で話したときのスライドです。構文解析を高速化するためには、すべての可能性を探索するのではなく、より文らしくなるような候補を先に探索することが有効です。
解析途中にどの選択肢を選ぶかを行動と考え、逆強化学習の枠組で解くことで、この高速化が達成できることを示しました。
同様のテクニックは、自然言語処理に限らず、探索問題全般に適用可能であり、面白いアプローチとして注目を集めています。

滞納債務の取り立て
(論文 http://www.prem-melville.com/publications/constrained-reinforcement-learning-kdd2010.pdf、
講演動画 http://videolectures.net/kdd2010_abe_odcucrl/)

税などの滞納債務の取り立てという問題に対して、債務者に対するアプローチ (督促状、電話など)
の手順を強化学習の枠組で学習する方法に関する、KDDI 2010 の論文です。IBMの安倍らが開発したシステム “Tax Collections Optimizer” は、ニューヨーク州の徴税部門で2009年12月から稼働しており、3年間で100万ドル以上の税収増の効果があると見積もられています。

強化学習を使ったデモ http://umichrl.pbworks.com/w/page/7597582/Demos-of-Reinforcement-Learning

Successes of RL http://rl-community.org/wiki/Successes_Of_RL

そのほか、こちらのページに多くの例が集積されていますので、ほかの例に興味のある人は参照してみてください。エレベーター制御、携帯電話基地局の電波割り当て、サプライチェーンマネジメントなど、多岐にわたる応用があることがわかると思います。

おわりに

本稿では、強化学習に関係するページやリソースを紹介しました。強化学習は、アルゴリズムから神経回路までを横断する、ある意味ではもっとも人工知能らしい研究領域といえます。これまでは、その問題設定の複雑さから、シミュレーション上での研究が多かった強化学習ですが、このブックマークの執筆を通じて、実世界に進出しつつあることを実感できました。このブックマークが、この分野に興味を持った人、研究に取り組む人の参考になれば幸いです。

謝辞

本稿の執筆に当たり、相談にのっていただきました Bayesian 強化学習研究会の皆様に感謝いたします。