アルゴリズムの設計を自動化することは、最適化問題を効率的に解く上で重要な課題です。セレクション・ハイパーヒューリスティクス（HH）は、最適化プロセスの各段階で複数の低レベルヒューリスティクスから最適なものを選択することで、この自動化を実現します。近年、標準的なベンチマーク関数に対するハイパーヒューリスティクスの性能に関する厳密な証明がいくつか発表されていますが、これらに採用されている学習メカニズムは、実世界のアプリケーションで一般的に使用される機械学習技術と比べてかなり簡略化されています。 本論文は、文献から選定した強化学習ハイパーヒューリスティクス（RLHH）を分析しています。これまでの唯一の先行研究では、広範なパラメータ設定の下でRLHHがLeadingOnesベンチマーク関数に対して適切なヒューリスティクスの選択を学習できないことが証明されていました。本論文では、適切なパラメータ値を使用すれば、RLS_1とRLS_2という2つのランダム局所探索演算子を備えたRLHHが、LeadingOnes関数を下位項を除いて最適な予想ランタイムで最適化できることを厳密に証明しています。 実験結果は、実際のサイズの問題に対して、RLHHが同様に最適な予想ランタイムを持つことが証明されていた一般化ランダムグラディエント・ハイパーヒューリスティクスよりも高速であることを示しています。この成果は、強化学習を用いたメタヒューリスティクス的アプローチの理論的な有効性を実証するもので、アルゴリズム選択の自動化における機械学習の可能性を示唆しています。