「スロットマシン10台の内、1台選んで1回プレイすることを100回繰り返して、どれが当たり確率が最も高いかを当ててください。」この問題は最適腕識別問題と呼ばれるバンディット問題です。当たり確率が最も高いスロットマシンを高確率で当てるためには「有望なマシンを優先的に試すこと」と「試行の偏りによる最適解の見落としを防ぐこと」の双方を両立した、バランスの取れた探索戦略が求められます。

　スロットマシンではなく、行動を選択する一般の最適腕識別問題においては、必要試行回数や誤識別率についての理論的な限界が既によく知られています。しかし、解決したい実問題の性質を前提とした新たな定式化を構築することで、より効率的な選択方策を設計することが可能となります。私は特に、選択可能な各行動がd次元ベクトルとして表現される問題(≒ブラックボックス最適化) や、行動評価のために階層的な最適腕識別が必要となる問題 (ゲームAI における「先読み」の実装など) といった、行動空間の構造に注目することで、より効果的な「有望な行動」の導出法や選択方策の構築を実現することを目指しています。

　アルゴリズム研究室では、このように逐次的に得られる情報を活用した行動選択の問題を数学的に定式化および解析し、これに基づいた最適な行動方策 (アルゴリズム) の設計を行うことを、主要な研究テーマの一つとしています。

　普段の活動内容としては、週2回の持ち回りのゼミ (輪読ゼミ、論文紹介ゼミ) と週1回の個別の面談を実施しています。研究はPCさえあればどこでも進められるため、必要に応じて研究室に来るなど、柔軟なスタイルで活動できます。研究室配属後は、各メンバーに個人用の席とPCが割り当てられます。768コアのクラスタ計算機や、2台のNVIDIA A6000を搭載したGPUサーバなど、計算機実験に必要な環境も整っています。

　研究内容やインターンなど、興味のある方はぜひお気軽にお問い合わせください。

　アルゴリズム研究室ホームページ: https://www-alg.ist.hokudai.ac.jp/