ICML98／UAI98／AAAI98 (7/24--30, 1998) 参加報告

国際会議全体について

今回のICMLはUAIおよびCOLTと合同で行われた。 ICMLが最も活気があり、UAIとCOLTはそれに便乗しているようにも見えた。 ICMLは2つのセッションが並列に進行し、全ての発表者は25分のプレゼンおよび ポスターセッションでの発表があった。 今回はSutton, Kaelbling, Singh, Littman, Moore, Mahadevan などの主だった 強化学習の研究者がほとんど顔を揃えた． またCMUのJ.Schneider(Mooreの弟子)やオーストラリアのPendrithという研究者らが 常連と化していた．

ICMLの直後にAAAI98があった． 近くのかなり大きな会議場へ会場を移して行われた。 全体の規模はAAAIの方がずっと大きく，多くの楽しいイベントがあった．

• Find Life on Mars：ロボットが火星に着陸したと想定して 岩などがごろごろあって，バンカーみたいな「危険ゾーン」などもある 12畳くらいの広さの区域を探索し，15分以内に生物に見立てた色付きの 小さな物体をつかんで着陸船まで持って来る競技
  Find Life on Mars競技におけるロボットの様子1
  Find Life on Mars競技におけるロボットの様子2
• Robot Interaction Event：7/29の夜にAIフェスティバルと称して立食パーティが 催され，会場では人ごみの中を4台のサーバーロボットが走り回った． ロボットはそれぞれ別の大学が製作しており，最も優れたロボットはどれか を人気投票で決める．
  パーティ会場のサーバロボットの人気投票のための投票箱
  パーティ会場のサーバロボット1
  パーティ会場のサーバロボット2
  パーティ会場のサーバロボット3
  パーティ会場のサーバロボット4
• Hall of Champions：人工知能と人間が実際にゲームで対戦する． ブリッジ，バックギャモン，scrabbleという3種類のゲームにおいて， AIの分野で有名なアルゴリズムと人間のチャンピオンが対戦していた．
• 企業や大学の研究室などがブースにおいてデモンストレーション
  例えば，トレーラトラックの後進制御や複数ロボットによる荷物集めなどを 実機を用いてデモ
  SONYのペットロボットを用いていた所もあった
  LEGOを用いたロボットによる競技の様子1
  LEGOを用いたロボットによる競技の様子2
  トレーラートラック後進制御用のLEGO実験装置
  トレーラートラック後進制御の実演
  フィールドに散らばるユニットを収集するLEGOロボットのデモ1
  フィールドに散らばるユニットを収集するLEGOロボットのデモ2
  フィールドに散らばるユニットを収集するLEGOロボットのデモ3
  フィールドに散らばるユニットを収集するLEGOロボットのデモ4
  フィールドに散らばるユニットを収集するLEGOロボットのデモ5
  SONYのAIBOを用いたデモ1
  形状記憶合金のアクチュエータを使った昆虫ロボット1
  形状記憶合金のアクチュエータを使った昆虫ロボット2

今回参加した国際会議において，推論や意志決定に関係するAI研究分野では， 不確実性を扱えるような枠組でなければ相手にもされず， 確率論や統計学の研究者がもてはやされている状況だった．

AIをロボットへ応用する研究では，移動ロボットのナビゲーションに関する ものが多かった．正確には，発表件数は少なかったがデモなどが多かった． また，(動)画像入力をセンサ入力としたAI制御などは見当たらなかった．

強化学習研究の動向

強化学習関連の発表は，ICMLで14件，AAAIで4件ほどあり、 研究者の関心を集める最もホットな分野であるが、 データマイニング等データベースからの知識獲得などの分野に比べると、 企業の利益に直接つながる応用は難しいという感じだった。

• Reinforcement Learning: How Far Can It Go? (Sutton, Invited Talk)
  強化学習の概要と今後の展開についての話． COLT/ICML/UAI合同のInvited Talkで， 広大な会場が大入り満員になるほどの盛況だった．
  • タスクをマルコフ決定過程(MDP)に変換するような状態表現， 行動表現，報酬表現，状態遷移表現を生成することがカギ
  • 状態遷移(transition)表現とは，状態遷移イベント発生などを 意味し，具体的にはセミマルコフ決定過程などに関係する．
  • 階層化も重要
• POMDP環境：
  • ［ICML］An Analysis of Direct Reinforcement Learning in Non-Markovian Domains, M.Pendrith and M.McGarity
    モンテカルロ法によるメモリレス強化学習の解析，POMDP, 平均\&割引報酬, 状態数無限の場合等
  • ［ICML］Using Eligibility Traces to Find the Best Memoryless Policy in Partially Observable Markov Decision Processes, J.Loch and S.Singh
    Sarsa(λ)を用いてグリッドワールドでの実験のみ
  • ［ICML］Learning sorting and decision trees with POMDPs, B.Bonet and H.Geffner
    Sortingと決定木の学習問題をPOMDP問題として定式化(強化学習ではない)
• 環境同定と報酬獲得のトレードオフ(Exploration and Exploitation trade-off):
  • ［ICML］Near-Optimal Reinforcement Learning in Polynomial Time, M.Kearns and S.Singh
    学習時間が限られる場合の強化学習，MDP，平均報酬，割引報酬
  • ［AAAI］Bayesian Q-learning, R.Dearden, N.Friedman and S.Russel
    報酬の確率分布を仮定することで，Q値の分布を考え，情報論的に適切な探査戦略の提案と収束の証明
• 複数種類の報酬：
  • ［ICML］Multi-Criteria Reinforcement Learning, C.Szepesvari, Z.Kalmar and Z.Gabor
    QLの更新式にうまく組み込んである
• マルチエージェント：
  • ［ICML］Multiagent Reinforcement Learning: Theoretical Framework and an Algorithm, J.Hu and M.Wellman
    ナッシュ均衡を最適とするQ-learning
  • ［AAAI］The Dynamics of Reinforcement Learning in Cooperative Multiagent Systems, C.Claus and C.Boutilier
    報酬に遅れが無い協調ゲームをQ-learningで解く．解析もある
• 階層化：
  • ［ICML］The MAXQ Method for Hierarchal Reinforcement Learning, T.Dietterich
    収束定理および実験
• セミマルコフ決定過程：
  • ［ICML］Intra-Option Learning about Temporally Abstract Actions, R.Sutton, D.Precup and S.Singh
    時間ステップは離散だが，イベント発生間隔は乱数
• プラニング+強化学習：
  • ［ICML］RL-TOPS: An Architecture for Modularity and Reuse in Reinforcement Learning, M.Ryan and M.Pendrith
    複雑なタスクを分割，状態をHigh, Lowの2階層で区別
  • ［AAAI］Applying Online Search Techniques to Continuous-State Reinforcement Learning, S.Davis, A.Y.Ng and A.Moore
    関数近似性能が低いため生じる不完全なValue Functionを， 環境モデル + online-searchで対処(連続な状態空間の扱いとも関連)
• 連続な状態空間の扱い
  • ［AAAI］Tree Based Discretization for Continuous State Space Reinforcement Learning, W.T.B.Uther and M.M.Veloso
    G-Algorithm (Chapman91) とU-Tree Algorithm (McCallum95) を改良した Continuous U-Treeアルゴリズムを提案． 連続値の状態入力を決定木によって各軸ごとに分割し，各ノードの状態遷移先 の情報を用いてさらに分割していく．Kolmogorov-Sminov 検定を利用．
• ゲーム：
  • ［ICML］Knightcap: A Chess Program that Learns by Combining TD(lambda) with Game-Tree Search, J.Baxter, A.Tridgell and L.Weaver
    TDLeaf($\lambda$)アルゴリズム (前期のゼミで坪井君が紹介)
    坪井君が作成した日本語訳資料をプレゼントしてきました． Baxterさんは``Oh, fantastic!''と喜んでました．
• 応用：
  • ［ICML］Learning to Drive a Bicycle Using Reinforcement Learning and Shaping, J.Randlov and P.Alstrom
    Sarsa(λ) + Replacing Trace を用いて自転車の制御
  • ［ICML］Value Function Based Production Scheduling, J.Schneider, J.Boyan, and A.Moore
    生産システムのスケジューリング問題をMDPの強化学習問題へ定式化
• その他：
  • ［ICML］A Learning Rate Analysis of Reinforcement Learning Algorithms in Finite-Horizon, F.Garcia and S.Ndiaye
    有限期間のQ-learning
  • ［ICML］Relational Reinforcement Learning, S.Dzeroski, H.Blockeel and L.De Raedt
    Inductive Logic Programming + 強化学習

Heuristicなアルゴリズムの提案に解析が伴わない場合は，大規模な問題に適用した 実験を示さないと論文が通りにくいようである． 理論的にしっかりした研究は通りやすいが，面白みが少ないためかそれだけでは インパクトが小さい． チェスの強化学習のように大規模なアプリケーションを扱った研究が 特に人気を集めていた．

連続な状態空間におけるValue Functionの関数近似の不完全性という問題意識が 出てきている点は面白い． この問題への対処方法として環境モデルとオンラインサーチを組み合わせるアイデア がDavisらによって示されているが，BaxterらのKnightcapもかなり似た 性質を持っている． 適正度の履歴を用いるActor-Criticでは，この問題に対して政策関数の適正度の履歴 を用いて対処している． それぞれのアプローチは組み合わせることも独立に動作させることも可能．

POMDPに関しては，単純なメモリレス強化学習法の意義が認められつつあるが， 完全なモンテカルロ法によってValueやQ値を推定する接近法が主流．

ICMLの会場でNIPS10の他，教科書を数冊購入． 階層化に関して，フラットなMDPから別のMDPへと問題を変換し， その変換されたMDPで最適化することによりフラットなMDPよりも 解の質は劣るが学習速度の点で優れるという報告があった． ICMLで発表された階層化は，このNIPS10中の報告に基づいていた． 階層の仕様はあらかじめ設計者が与える．

MEMO

映像記録