技術的概要：組合せ最適化のための TreeDQN

問題定義

組合せ最適化タスク、特に混合整数線形計画（MILP）は、頻繁に分枝限定法（B&B）アルゴリズムを用いて解かれます。B&B の効率性は、ノード選択（次に評価する部分問題をどのものにするか選択）と変数選択（どの変数を分割するか選択）という 2 つの意思決定プロセスに大きく依存します。人間が設計したヒューリスティック（例：Strong Branching）は存在しますが、計算コストが高すぎるか、特定のタスク分布に適応していないことがよくあります。

強化学習（RL）は、最適な分枝則を学習するための道を提供します。しかし、標準的な RL を B&B に適用することは容易ではありません。なぜなら、B&B プロセスは状態の線形系列ではなく、木構造を生成するからです。標準的なマルコフ決定過程（MDP）は、1 つの行動に対して単一の次の状態を仮定しますが、B&B の分枝は複数の子ノードを作成します。これを**木 MDP（tMDP）**としてモデル化する既存のアプローチは、以下の重大な課題に直面してきました：

1. サンプル非効率性: オンポリシー手法（例：tMDP+DFS）は、各勾配ステップごとに新しい MILP インスタンスを解く必要があり、訓練時間が許容できないほど長くなります。
2. 高い分散: 生成される木サイズの分布は、極めて高い分散を持つ長尾分布です。算術平均（標準的な MSE 損失）を最適化することは、稀に発生する極めて大きな木に対して敏感であり、不安定な訓練と汎化性能の低下を招きます。
3. 理論的収束性の欠如: 木 MDP の文脈におけるベルマン作用素の収束を証明する厳密な理論的証拠はありませんでした。

手法：TreeDQN

著者は、木 MDP に適応したサンプル効率の高いオフポリシー深層 Q ネットワークであるTreeDQNを提案します。この手法は、3 つの中核的な技術的要素を統合しています：

1. 経験再生を用いたオフポリシー学習

単一の更新後にデータを破棄するオンポリシー手法とは異なり、TreeDQN は経験再生バッファを利用します。これは、$(s_t, a_t, r_t, s^+_{t+1}, s^-_{t+1})$ の形式で遷移を格納します。ここで、$s^+$ と $s^-$ は分枝行動によって生成された左右の子ノードを表します。これにより、エージェントは過去の経験から学習でき、訓練中に必要な MILP 解決回数を大幅に削減できます。

2. 理論的正当性：平均収縮

木構造におけるベルマンバックアップの利用を支持するため、著者は木ベルマン作用素が平均収縮（contracting in mean）することを証明しました。

• 定義: 作用素 $T$ が平均収縮するとは、$\|TV - TU\|_\infty = p \cdot \|V - U\|_\infty$ であり、期待値 $E[p] < 1$ となることを指します。
• 証明の論理: 有限の根付き木において、辺の数はノード数より 1 つ少ないです。したがって、ノードあたりの子ノード数の期待値は $(K-1)/K < 1$ となります。これにより、平均的にベルマン作用素が価値関数を収縮させることが保証され、この特定の設定における Q 学習更新の収束に対する理論的基盤が提供されます。
• 精緻化: 論文はまた、状態依存の分枝に関する命題を提供しており、最大期待分枝係数 $p_{max}$ が $\gamma p_{max} < 1$ を満たす場合、作用素は sup ノルムにおいて収縮となることを示しています。

3. 損失関数：幾何平均の最適化

木サイズが長尾分布に従うことを踏まえ、著者は算術平均（平均二乗誤差による）の最適化は最適ではないと主張します。代わりに、**平均対数二乗誤差（MSLE）**の最小化を提案します。

• メカニズム: 損失関数は $L(y, t) = \frac{1}{B} \sum (\log|y| - \log|t|)^2$ と定義されます。
• 効果: MSLE を最小化することは、期待リターンの幾何平均を最適化することに相当します。これによりターゲットの動的範囲が圧縮され、稀に発生する極めて大きな木（外れ値）に対する感度が低下し、訓練プロセスが安定します。
• 実装: Q ネットワークは、木サイズの大きな範囲を数値的に処理するために指数活性化関数（$f = -\exp(\cdot)$）を使用します。ターゲット値は $r - \exp(Q_{target}(s^+)) - \exp(Q_{target}(s^-))$ として計算され、損失はこれらの値の対数に基づいて計算されます。

主要な貢献

1. アルゴリズムの提案: 木構造に適応した経験再生を利用し、B&B における変数選択のための最初の成功したオフポリシー RL アルゴリズムであるTreeDQNの導入。
2. 理論的貢献: 木 MDP に対するベルマン作用素が平均収縮することを証明し、この特定のクラスの問題に対する最初の理論的収束保証を提供。
3. 損失関数の革新: 帰還の幾何平均を最適化する MSLE ベースの損失関数の開発。木サイズ分布の高い分散を効果的に処理し、訓練を安定化。
4. 実証的性能: TreeDQN が既存のオンポリシー手法に比べて最大10 倍少ない訓練データを必要とし、合成および実用的なベンチマークの両方で最先端の手法を上回ることを実証。

実験結果

合成タスク

著者は、TreeDQN を 5 つの NP 困難タスク（組合せオークション、集合被覆、最大独立集合、施設配置、多重ナップサック）で評価しました。

• 訓練効率: TreeDQN は、オンポリシーベースライン（tMDP+DFS）およびオフポリシーベースライン（FMSTS）よりもはるかに早く最良のチェックポイントに到達しました。例えば、集合被覆タスクにおいて、TreeDQN は 800 エピソードで達成したのに対し、FMSTS は 3,000 エピソード、tMDP+DFS は 30,000 エピソードを要しました。
• 性能: TreeDQN は、Strong Branching、模倣学習（IL）、および他の RL 手法と比較して、より低い幾何平均の木サイズと実行時間を達成しました。
• 統計的有意性: ウィルコクソンの符号付き順位和検定により、TreeDQN のベースラインに対する性能向上が、ほとんどのタスクで統計的に有意であることが確認されました。
• 転移学習: より大きな「転移」インスタンスでテストされた際、TreeDQN は一般的に FMSTS や tMDP+DFS を上回りましたが、性能はタスクの複雑さによって変動しました。優先度付き経験再生の使用は、最大独立集合のような困難なタスクにおけるロバスト性をさらに向上させました。

実世界への応用（ML4CO コンペティション）

TreeDQN は、ML4CO コンペティションのバランスドアイテム配置タスクに適用されました。これは、複雑な多次元マルチナップサック問題です。

• 報酬指標: 木サイズの最小化が目的であった合成タスクとは異なり、ここでは最適解が時間制限内で到達不可能であったため、報酬は双対積分（双対境界曲線下の面積）でした。
• 結果: わずか500 エピソードで訓練された TreeDQN は、SCIP デフォルトソルバ、Strong Branching、および模倣学習エージェントを大幅に上回りました。
• 効率性: TreeDQN は、IL に比べてはるかに少ない線形計画（LP）部分問題を解きながら、最高の双対境界と原始境界の改善を達成し、優れたサンプル効率を実証しました。

意義と主張

この論文は、TreeDQN が教師あり模倣学習（推論は速いがエキスパートを上回れない）とオンポリシー RL（エキスパートを上回れるがサンプルを大量に必要とする）の間のギャップを埋めると主張しています。

• 実用的影響: TreeDQN は、MILP 解決回数を大幅に減らしてタスク固有の分枝ヒューリスティックを学習可能にし、リアルタイムまたはリソース制約のある訓練環境での実用性を可能にします。
• 方法的進歩: 以前は木構造 MDP への適用が困難と考えられていたオフポリシー深層 RL 手法が、経験再生、理論的に正当化された収縮特性、そして組合せ指標（幾何平均）と整合した最適化目的の組み合わせを通じて、安定かつ効果的にできることを実証しました。
• 初の成功: 著者は、TreeDQN が ML4CO コンペティションの複雑なバランスドアイテム配置タスクに対して効率的な変数選択方策を学習した最初の成功した RL アルゴリズムであり、従来のヒューリスティックおよび模倣学習を上回ることを強調しています。

著者は、この手法が類似の MILP タスクの分布向けに設計されているものの、実用的でデータ効率の良い分枝ヒューリスティックの学習に向けた重要な一歩であり、模倣学習とオンポリシー RL の間の性能ギャップを埋めるものであると結論付けています。