Optimal Hidden-Target Learning for Online Inventory Optimization on General Convex Sets

技術要約：一般的な凸集合におけるオンライン在庫最適化のための最適な隠れたターゲット学習

問題定式化
本論文は、物理的な在庫制約に従いつつ、容量集合 $Y \subseteq \mathbb{R}^n_+$ から発注ベクトル $y_t$ を選択するオンライン在庫最適化（OIO）を取り扱う。標準的なオンライン凸最適化（OCO）とは異なり、OIOには「物理的メモリ」が存在する。すなわち、時刻 $t$ における実行可能集合 $J_t = Y \cap \{y \mid y \succeq x_t\}$ は、現在の在庫状態 $x_t$ に依存する。在庫は繰り越されるため、学習者は、結果として得られるベクトルが現在のストックレベルを下回る場合、単に $Y$ への勾配ステップを投影するだけでは不十分である。環境は敵対的な需要 $d_t$ と損失関数 $\ell_t$ を選択し、学習者は比較対象のシーケンスに対して動的または静的な後悔（リグレット）を最小化することを目指す。

MaxCOSD (Hihat et al., 2023) などの先行研究は、適応的なサイクルを用いて一般的な凸容量集合を扱ってきたが、その静的後悔は UPPD（一様確率正の需要）条件の下で $\tilde{O}(\sqrt{T/\mu})$ であった。しかし、この $1/\mu$（$\mu$ は共通の需要ショックの確率）への依存度は最適ではなく、既存の隠れたターゲット（hidden-target）手法は、製品ごとの「売り切れ（sell-out）」分析への依存により、線形容量制約に限定されていた。

手法：ノルム整合型隠れたターゲット投影
著者らは、特定の幾何学的フレームワークを利用すれば、単純な原理である「隠れたターゲット $z_t$ を維持し、それを実行可能集合 $J_t$ に投影する」という手法が、一般的な凸集合に対しても十分であることを提案している。

1. アルゴリズム: 学習者は、ベースとなるオンライン学習アルゴリズム（例：オンライン勾配降下法）によって生成される隠れたターゲット・シーケンス $z_t \in Y$ を維持する。実装されるアクションは、$y_t = \text{Proj}_{J_t}^{\|\cdot\|}(z_t)$、すなわち特定のノルム $\|\cdot\|$ で測定された $J_t$ への $z_t$ の投影である。
2. ノルム整合の原則: 重要な手法論的貢献は、投影ノルム、キューの状態測定、およびターゲットの移動指標がすべて、同一の許容ノルム $\|\cdot\|$ を使用する必要があるという点である。許容ノルムは $\ell_\infty$ ノルムを支配する（すなわち $\|x\|_\infty \le \|x\|$）。
3. 幾何学的キュー減少: 分析の核心は、「ターゲットと実装のギャップ」を $q_t = \|z_t - y_t\|$ と定義することである。著者らは、以下のパスワイズな幾何学的再帰（リンドレー・キュー）を証明している：
   $$q_{t+1} \le [q_t + \|z_{t+1} - z_t\| - d^{\min}_t]_+$$
   ここで $d^{\min}_t = \min_i d_{t,i}$ は共通の需要である。
   • 解釈: ギャップは一つの次元のキューとして進化する。隠れたターゲットの移動（$z_{t+1} - z_t$）は「到着」として機能し、共通の需要（$d^{\min}_t$）は「サービス」として機能する。
   • 意義: この減少により、複雑で状態依存的な実行可能性の問題が、スイッチングコストが付加された標準的な OCO 問題へと変換される。これにより、従来の曲面を持つ凸集合への拡張を阻んでいた、製品ごとの会計処理や線形制約の必要性を回避できる。

主な貢献と結果

1. 凸損失に対する最適な静的後悔:
   ベースとなる学習者にオンライン勾配降下法（OGD）を用いることで、本論文は $\tilde{O}(\sqrt{T/\mu})$ の静的後悔を達成する。これは、一般的な凸集合における最良の既知の保証を $O(1/\mu)$ から $O(1/\sqrt{\mu})$ へと改善するものである。著者らは、これと一致する下界 $\Omega(\sqrt{T/\mu})$ を証明し、UPPD 下でのこれがミニマックス最適であることを確立した。

2. 強凸損失に対する多項式対数（Polylogarithmic）の後悔:
   $\alpha$-強凸損失に対して、同一のフレームワークは $\tilde{O}(\log(T/\mu))$ の後悔界をもたらす。これは、一般的な容量集合を持つ敵対的 OIO において、多項式対数の後悔が達成可能かという未解決問題に回答するものである。

3. 改善された動的後退:
   本手法は、比較対象の $\ell_1$ 変分 $P_{T,1}$ ではなく、ユークリッド・パス変分 $P_{T,2}$ に依存する動的後悔の保証を提供する。これにより、$n^{1/4}$ という明示的な因子が除去され、密な比較対象の動きに対する境界が鋭利になる。著者らは、既知の変分には標準的な OGD を、未知の変分には平滑化 OGD (SOGD) を用いてこれらの結果を得ている。

4. ミラー降下法による幾何学に敏感な洗練:
   本フレームワークは、強凸正則化を用いたオンライン・ミラー降下法（OMD）へと拡張されている。これにより、容量集合 $Y$ の特定の幾何学や勾配の双対ノルムに適応した後悔界を得ることができる。例えば、線形制約に対してエントロピー正則化を使用することで、勾配が座標方向に密な場合において、ユークリッド投影と比較して次元 $n$ への依存度を改善できる。

5. 次元フリーの保証:
   結果は標準的な OCO の意味で次元フリーである。次元 $n$ は、明示的な乗法的因子（例：$n^{1/4}$）としてではなく、問題のパラメータ（$Y$ の直径や勾配の境界など）を通じてのみ現れる。

意義と主張
本論文は、「隠れたターゲット投影」の原理が、適切な「ノルム整合型」の幾何学的分析と組み合わされたとき、一般的な凸容量 OIO モデルに対して理論的に最適であるということを主張している。

• 理論的統一: 本研究は、物理的な実行可能性制約をベースとなる学習アルゴリズムから切り離せることを示すことで、在庫管理と標準的な OCO を統一する。在庫レイヤーは、ベースとなる学習者が在庫力学を理解する必要なく、ベースとなる学習者にスイッチングコストを課すキュー消去メカニズムとして機能する。
• 障害の解決: 製品ごとの誤差に関する保存恒等性の欠如といった、一般的な凸集合へのキューイング分析の拡張を妨げていた障害を、状態を単一の許容ノルムにおける幾何学的距離として測定することで回避できることを示している。
• 実証的検証: 合成データおよび実世界の M5 予測コンペティション・データを用いた実験により、提案された HT-OGD アルゴリズムが、線形および曲面容量設定の両方において、MaxCOSD や DDM（製品ごとの手法）よりも優れた性能を示すことが確認され、理論的な後悔界の改善が裏付けられた。

著者らは、隠れたターゲットの学習と、ノルム整合型キューによる物理的実行可能性の強制を分離するというこのモジュール型のテンプレートが、将来の「状態依存制約を持つオンライン問題」のための堅牢なフレームワークを提供すると結論付けている。