研究成果の紹介

安全性や経済性の観点から，シミュレーション上で強化学習を実施して，得られた方策を現実環境で運用する，という方針がしばしば採用されます．とりわけ，強化学習において深層学習技術を採用した深層強化学習の枠組みでは，方策を学習するために必要な環境とエージェントのインタラクション数が膨大になるため，シミュレーションの活用は必要不可欠といえます．しかし，シミュレーションでは運用時の現実環境を完全に表すことが出来ない，現実環境が時々刻々と変化してしまう，などの理由から，学習時に使用したシミュレーション環境と運用時の現実環境には差が生じてしまいます．この差によって，シミュレーション上で学習された方策が，現実環境では低性能で安全性に問題のある方策となる恐れがあります．

私達は，シミュレーションと現実環境の差を考慮した強化学習の検討をしています．[IJCNN 2022]では，シミュレーションと現実環境での状態の表現方法の差に着目し，シミュレーション上で得られた方策を現実環境に転移するための方法を提案しています．[NeurIPS 2022]では，状態遷移確率と報酬関数の差に着目し，考えうる最悪なケースでの性能を最大化するような強化学習アプローチを提案しています．

文献：

[IJCNN 2022] Rei Sato, Kazuto Fukuchi, Jun Sakuma, Youhei Akimoto. Few-Shot Image-to-Semantics Translation for Policy Transfer in Reinforcement Learning, 2022 International Joint Conference on Neural Networks (IJCNN), (2022) To appear.

[NeurIPS 2022] Takumi Tanabe, Rei Sato, Kazuto Fukuchi, Jun Sakuma, Youhei Akimoto. Max-Min Off-Policy Actor-Critic Method Focusing on Worst-Case Robustness to Model Misspecification, Advances in Neural Information Processing Systems 35 (NeurIPS 2022), (2022) Accepted.

シミュレーションベース最適化では，まず現実環境をモデル化したシミュレータを設計し，そのシミュレータのもとで計算される目的関数を最適化することになります．しかし，現実環境をモデル化する際には，現実環境の不確実性により，運用を想定している環境を正確にモデル化することが困難な場合はしばしば見受けられます．必ずしも正しくない推定モデルにおいて最適化した結果は，これを現実世界で運用した場合に想定したパフォーマンスが得られないばかりか，致命的な欠陥を起こすことも考えられます．そのため，最適化結果の信頼性の観点から，モデルの不確実性を考慮したロバスト解を得ることが望まれます．

私達は，このようなモデルの不確実性を考慮したシミュレーションベース最適化を実現する最適化法の開発 [GECCO 2021a, 2021b, 2022a]やその応用事例 [GECCO 2019, ACM TELO 2022] の研究をしています．

文献：

[GECCO 2019] Atsuhiro Miyagi, Youhei Akimoto, Hajime Yamamoto. Well Placement Optimization under Geological Statistical Uncertainty, Proceedings of the Genetic and Evolutionary Computation Conference (GECCO ’19), July 13–17, 2019, Prague, Czech Republic, pages 1284-1292 (2019)

[GECCO 2021a] Atsuhiro Miyagi, Kazuto Fukuchi, Jun Sakuma, Youhei Akimoto. Adaptive Scenario Subset Selection for Minimax Black-Box Continuous Optimization, GECCO '21: Proceedings of the Genetic and Evolutionary Computation Conference, pages 697-705 (2021) [doi]

[GECCO 2021b] Youhei Akimoto. Saddle Point Optimization with Approximate Minimization Oracle, GECCO '21: Proceedings of the Genetic and Evolutionary Computation Conference, pages 493-501 (2021) [doi] [preprint] [repository]

[ACM TELO 2022] Youhei Akimoto, Yoshiki Miyauchi, Atsuo Maki. Saddle Point Optimization with Approximate MinimizationOracle and its Application to Robust Berthing Control, ACM Transactions on Evolutionary Learning and Optimization 2(1), pages 1-32 (2022) [doi] [link] [preprint] [repository]

[GECCO 2022a] Atsuhiro Miyagi, Kazuto Fukuchi, Jun Sakuma, Youhei Akimoto. Black-Box Min–Max Continuous Optimization Using CMA-ES with Worst-case Ranking Approximation, GECCO '22: Proceedings of the Genetic and Evolutionary Computation Conference, (2022) [doi] [repository]

近年，深層学習は非常に広い応用を見せています．深層学習の性能は，そこで用いられる深層ニューラルネットワークのアーキテクチャ（各部分で利用されるオペレーションや，ネットワークの接続状態など）に依存します．Neural Architecture Search (NAS) は，これまでの人手によるアーキテクチャ設計を，探索アルゴリズムによって自動化する AutoML（自動機械学習）の一分野です．

私達は，One-shot NASと呼ばれる，ネットワークのアーキテクチャとパラメータを一度の学習サイクルにおいて同時に最適化する枠組みの研究をしています．とりわけ，確率緩和と呼ばれる方法によるパラメータの連続空間への拡張と，連続化されたパラメータ空間上の推定勾配を用いたアーキテクチャ探索の方法に着目しています．

アーキテクチャの探索に自然勾配を活用した方法[AAAI 2018]やその一般化と勾配ステップサイズの適応規則の提案[ICML 2019]，貢献度分配の考え方を導入することによる勾配推定分散の削減とそれによる探索高速化[JSAI 2019, AAAI 2021]などの成果があります．

文献：

[AAAI 2018] Shinichi Shirakawa, Yasushi Iwata, Youhei Akimoto. Dynamic Optimization of Neural Network Structures Using Probabilistic Modeling, Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, New Orleans, Louisiana, USA, February 2-7, 2018, pages 4074-4082 (2018)

[ICML 2019] Youhei Akimoto, Shinichi Shirakawa, Nozomu Yoshinari, Kento Uchida, Shota Saito, Kouhei Nishida. Adaptive Stochastic Natural Gradient Method for One-Shot Neural Architecture Search, Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, pages 171-180 (2019)

[JSAI 2019] 佐藤 怜, 秋本 洋平, 佐久間 淳, 貢献度分配を導入した方策勾配によるNeural Architecture Searchの高速化, 人工知能学会全国大会論文集, 2019, JSAI2019 巻, 第33回全国大会(2019), セッションID 2P3-J-2-02. 全国大会学生奨励賞受賞

[AAAI 2021] Rei Sato, Jun Sakuma, Youhei Akimoto. AdvantageNAS: Efficient Neural Architecture Search with Credit Assignment, Proceedings of the AAAI Conference on Artificial Intelligence, 35(11), pages 9489-9496 (2021) [link] [repository]

進化戦略（Evolution Strategy）は連続値の最適化において広く用いられている進化計算アルゴリズムの一つです．連続値最適化のための進化計算アルゴリズムのほとんどは，理論解析が困難であることから，収束の保証を持ちません．

本研究では，離散値最適化の解析にしばしば用いられるDrift Analysisの方法を連続値最適化においても利用できるように拡張し，(1+1)-ES with 1/5-success ruleと呼ばれる有名なアルゴリズムに適用しました．[GECCO 2021]では，凸二次関数において，一般的な勾配法と同様の一次収束が保証できること，そのときの収束率が設計変数の数に反比例すること，また，ヘッセ行列の固有値分布と収束率の関係を示すことに成功しました．[FOGA 2019, SIOPT 2022]では，強凸かつ勾配がリプシッツ連続な関数（勾配ベースの最適化法の解析においてしばしば仮定される関数クラス）において一次収束を示しています．勾配法の解析と同程度に一般的な関数クラスでの一次収束を進化戦略において示したのは，本研究が世界で初めてです ．

文献：

[GECCO 2018] Youhei Akimoto, Anne Auger, and Tobias Glasmachers. 2018. Drift theory in continuous search spaces: expected hitting time of the (1 + 1)-ES with 1/5 success rule. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '18), Hernan Aguirre (Ed.). ACM, New York, NY, USA, 801-808.

[FOGA 2019] Daiki Morinaga, Youhei Akimoto. Generalized drift analysis in continuous domain: linear convergence of (1 + 1)-ES on strongly convex functions with Lipschitz continuous gradients, Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, pages 13-24 (2019) [doi] [link] Best Paper Award

[GECCO 2021] Daiki Morinaga, Kazuto Fukuchi, Jun Sakuma, Youhei Akimoto. Convergence Rate of the (1+1)-Evolution Strategy with Success-Based Step-Size Adaptation on Convex Quadratic Function, GECCO '21: Proceedings of the Genetic and Evolutionary Computation Conference, pages 1169-1177 (2021) [doi] [preprint]

[SIOPT 2022] Youhei Akimoto, Anne Auger, Tobias Glasmachers, Daiki Morinaga. Global Linear Convergence of Evolution Strategies on More than Smooth Strongly Convex Functions, SIAM Journal on Optimization 32(2), pages 1402-1429 (2022) [doi] [preprint]

[SPA 2022] Youhei Akimoto, Anne Auger, Nikolaus Hansen. An ODE Method to Prove the Geometric Convergence of Adaptive Stochastic Algorithms, Stochastic Processes and their Applications 145, pages 269-307 (2022) [doi] [preprint]

進化戦略（Evolution Strategy）は連続値の最適化において広く用いられている進化計算アルゴリズムの一つです．とりわけ，多変量正規分布からの候補解生成と平均ベクトルおよび共分散行列の更新を繰り返すことで最適化を進める Covariance Matrix Adaptation Evolution Strategy (CMA-ES) は，ブラックボックス連続最適化に対する最も有力な方法の一つとして広く用いられています．

CMA-ESの強みは，その不変性にあります．CMA-ESは目的関数の単調変換や設計変数空間のアフィン変換に対して不変であることから，目的関数の不連続性や変数間依存性・悪スケール性といったよく知られる困難さに対して有効であることが示されています．多変量正規分布の共分散行列を適応することは，変数間依存性や悪スケール性に対応するために必要ですが，特に高次元の場合には時間的および空間的計算量，最適化に必要なシミュレーション回数の観点から，その学習時間が最適化のボトルネックとなります．Deep Neural Networkを用いた進化的強化学習法（Deep NeuroEvolution）や自由度の高いトポロジー最適化などのように，数千を超える変数のブラックボックス最適化が求められるようになってきているため，最適化法の高速化が求められています．

私達は，CMA-ESをいくつかの観点から高速化するための方法を提案しています．

[ECJ 2020]では，共分散行列の適応を高速化する３つの独立したアイディアを提案しています．これらにより，従来のCMA-ESの強みを犠牲にすることなく，実用上多くの最適化問題に見られる性質を有する問題において大幅な効率改善が見られることを実験的に確認しています．問題の性質（変数分離可能性など）ごとに効率的に最適化可能なアルゴリズムは異なります．しかし，問題ごとに適切なアルゴリズムを選択することは，ブラックボックス最適化においては感と経験を要します．本研究の成果は，アルゴリズム選択の困難さを解決することに一役買っています．

[GECCO 2014, GECCO 2016, PPSN 2016]では，高次元最適化において変数間の相関関係が変数の数に対して線形のパラメータ数によって表現される（目的関数のヘッセ行列が対角行列や低ランク行列の和や積によって表現される）という仮定を置くことで，時間的計算量と空間的計算量を変数の数に対して線形に抑えつつ，従来よりも少ないシミュレーション回数で最適化する方法を提案しました．連続値の最適化に対して優れているCMA-ESと比較して，計算時間とメモリ使用量の両者において優れていることが実験的に示されています．[GECCO 2014]ではVD-CMAおよび[GECCO 2016]ではVkD-CMAと呼ばれる方法を提案しています．VkD-CMAにおいてk=1とした場合，両者は類似していますが，経験的にはVD-CMAよりもVkD-CMA(k=1)の方が安定して速い収束を示します．

文献：

[GECCO 2014] Youhei Akimoto, Anne Auger, and Nikolaus Hansen. 2014. Comparison-based natural gradient optimization in high dimension. In Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation (GECCO '14). ACM, New York, NY, USA, 373-380. [PDF with proofs] [Python code]

[GECCO 2016] Youhei Akimoto and Nikolaus Hansen. 2016. Projection-Based Restricted Covariance Matrix Adaptation for High Dimension. In Proceedings of the Genetic and Evolutionary Computation Conference 2016 (GECCO '16), Tobias Friedrich (Ed.). ACM, New York, NY, USA, 197-204. [Python code]

[PPSN 2016] Akimoto Y., Hansen N. (2016) Online Model Selection for Restricted Covariance Matrix Adaptation. In: Handl J., Hart E., Lewis P., López-Ibáñez M., Ochoa G., Paechter B. (eds) Parallel Problem Solving from Nature – PPSN XIV. PPSN 2016. Lecture Notes in Computer Science, vol 9921. Springer, Cham [Python code] Best Paper Nomination

[ECJ 2020] Youhei Akimoto, Nikolaus Hansen. 2020. Diagonal Acceleration for Covariance Matrix Adaptation Evolution Strategies. Evolutionary Computation, vol. 28, no. 3, pages 379--404. [Python code]

シミュレーションベース最適化において，制約条件はしばしばペナルティ関数法やこれに準ずる方法がその汎用性や容易さから採用されています．私達の研究[GECCO 2019] においても，修正オペレータと適応的ペナルティ関数法に基づく制約対処法を提案しています．しかし，制約条件を満たす領域（実行可能領域）が探索空間全体に対して（測度の観点で）狭い複数の非連結な集合となっているような場合 [GECCO 2020] や，そもそも制約条件を明示的に表現することが難しいような場合 [GECCO 2021] には，これらの方法が有効でない場面が見受けられます．

私達は，このような場面を想定し，深層生成モデルを活用した制約付きシミュレーションベース最適化のための最適化フレームワークを設計しています．深層生成モデルは，何らかの潜在空間からデータ空間への写像を深層ニューラルネットワークを用いて表現します．私達の方法では，データ空間を制約を満たす実行可能領域，潜在空間を最適化法が探索する設計変数空間に対応付けます．このような深層生成モデルを最適化に先立って学習しておくことで，制約を満たした解を探索することが可能となります．

[GECCO 2020]では，制約条件を明示的に書き下すことが可能な問題を対象に，実行可能領域が非連結集合となる場合に，対応する潜在空間が連結集合になるように深層生成モデルを学習する方法を提案しています．[GECCO 2021]では，Angry Birds というビデオゲームのレベル（ステージ）生成問題を対象に，「プレイ可能であり自然なレベルである」という暗黙の制約条件を満たすように，この条件を満たしているであろう既存のレベルを訓練データとして深層生成モデルを学習する方法を提案しています．

文献：

[GECCO 2019] Naoki Sakamoto, Youhei Akimoto. Adaptive Ranking Based Constraint Handling for Explicitly Constrained Black-Box Optimization, Proceedings of the Genetic and Evolutionary Computation Conference (GECCO ’19), July 13–17, 2019, Prague, Czech Republic, pages 700-708 (2019). Best Paper Nomination

[GECCO 2020] Naoki Sakamoto, Eiji Semmatsu, Kazuto Fukuchi, Jun Sakuma, Youhei Akimoto. 2020. Deep Generative Model for Non-convex Constraint Handling, GECCO '20: Proceedings of the 2020 Genetic and Evolutionary Computation Conference, pages 636-644 (2020)

[GECCO 2021] Takumi Tanabe, Kazuto Fukuchi, Jun Sakuma, Youhei Akimoto. 2021. Level Generation for Angry Birds with Sequential VAE and Latent Variable Evolution. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '21), To appear. Best Paper Nomination

[ECJ 2022] Naoki Sakamoto, Youhei Akimoto. Adaptive Ranking-based Constraint Handling for Explicitly Constrained Black-Box Optimization, Evolutionary Computation, (2022) [doi] [preprint] [repository]