論文の概要: Online Linear Programming with Replenishment

• arxiv url: http://arxiv.org/abs/2601.14629v1
• Date: Wed, 21 Jan 2026 04:09:29 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-22 21:27:50.228564
• Title: Online Linear Programming with Replenishment
• Title（参考訳）: Replenishmentによるオンライン線形プログラミング
• Authors: Yuze Chen, Yuan Zhou, Baichuan Mo, Jie Ying, Yufei Ruan, Zhou Ye,
• Abstract要約: オンライン線形プログラミング(OLP)モデルについて検討し、在庫を事前に提供せず、補充プロセスを通じて徐々に到着する。 分散された不確実な補充の導入は、古典的なALPの構造を根本的に変える。 我々は,ALP文献で研究されている3つの主要な分布系について,新しいアルゴリズムと後悔の分析法を開発した。
• 参考スコア（独自算出の注目度）: 9.214452378957697
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study an online linear programming (OLP) model in which inventory is not provided upfront but instead arrives gradually through an exogenous stochastic replenishment process. This replenishment-based formulation captures operational settings, such as e-commerce fulfillment, perishable supply chains, and renewable-powered systems, where resources are accumulated gradually and initial inventories are small or zero. The introduction of dispersed, uncertain replenishment fundamentally alters the structure of classical OLPs, creating persistent stockout risk and eliminating advance knowledge of the total budget. We develop new algorithms and regret analyses for three major distributional regimes studied in the OLP literature: bounded distributions, finite-support distributions, and continuous-support distributions with a non-degeneracy condition. For bounded distributions, we design an algorithm that achieves $\widetilde{\mathcal{O}}(\sqrt{T})$ regret. For finite-support distributions with a non-degenerate induced LP, we obtain $\mathcal{O}(\log T)$ regret, and we establish an $Ω(\sqrt{T})$ lower bound for degenerate instances, demonstrating a sharp separation from the classical setting where $\mathcal{O}(1)$ regret is achievable. For continuous-support, non-degenerate distributions, we develop a two-stage accumulate-then-convert algorithm that achieves $\mathcal{O}(\log^2 T)$ regret, comparable to the $\mathcal{O}(\log T)$ regret in classical OLPs. Together, these results provide a near-complete characterization of the optimal regret achievable in OLP with replenishment. Finally, we empirically evaluate our algorithms and demonstrate their advantages over natural adaptations of classical OLP methods in the replenishment setting.
• Abstract（参考訳）: 本稿では,オンライン線形プログラミング(OLP)モデルについて検討する。 この補充ベースの定式化は、電子商取引のフルフィルメント、パーシライズ可能なサプライチェーン、資源が徐々に蓄積され、初期在庫が小さく、ゼロとなる再生可能エネルギーシステムといった運用環境を捉えている。 分散した不確実な補充の導入は、古典的なOLPの構造を根本的に変え、持続的なストックアウトリスクを生み出し、全予算の事前知識を排除します。 我々は,ALP文献で研究されている3つの主要な分布系,すなわち有界分布,有限支持分布,および非退化状態の連続支持分布に対する新しいアルゴリズムと後悔の解析を開発した。 有界分布に対しては、$\widetilde{\mathcal{O}}(\sqrt{T})$ regretを達成するアルゴリズムを設計する。 非退化 LP を持つ有限支持分布に対しては、$\mathcal{O}(\log T)$ regret を得るとともに、退化インスタンスに対して $Ω(\sqrt{T})$ lower bound を成立させ、$\mathcal{O}(1)$ regret が達成可能な古典的な設定から鋭い分離を示す。 連続的に支援された非退化分布に対して、古典的 OLP における $\mathcal{O}(\log^2 T)$ regret に匹敵する $\mathcal{O}(\log T)$ regret を達成する2段階累積変換アルゴリズムを開発する。 これらの結果は, 補充を伴うALPで達成可能な最適後悔のほぼ完全な特徴を与えるものである。 最後に,我々のアルゴリズムを実証的に評価し,補充設定における古典的ALP手法の自然適応に対する利点を実証する。

関連論文リスト

• Learning Intersections of Two Margin Halfspaces under Factorizable Distributions [56.51474048985742]
  ハーフスペースの交叉学習は計算学習理論における中心的な問題である。 たった2つのハーフスペースであっても、学習が時間内に可能かどうかという大きな疑問が残る。 本稿ではCSQ硬度障壁を確実に回避する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-11-13T00:28:24Z)
• Towards a Sharp Analysis of Offline Policy Learning for $f$-Divergence-Regularized Contextual Bandits [49.96531901205305]
  我々は$f$-divergence-regularized offline policy learningを分析する。 逆Kullback-Leibler (KL) の発散に対して、単極集中性の下での最初の$tildeO(epsilon-1)$サンプル複雑性を与える。 これらの結果は,$f$-divergence-regularized policy learningの包括的理解に向けて大きな一歩を踏み出したものと考えられる。
  論文  参考訳（メタデータ） (2025-02-09T22:14:45Z)
• A Pseudo-Semantic Loss for Autoregressive Models with Logical Constraints [87.08677547257733]
  ニューロシンボリックAIは、純粋にシンボリックな学習とニューラルな学習のギャップを埋める。 本稿では,ニューラルネットワークの出力分布に対するシンボリック制約の可能性を最大化する方法を示す。 また,スドクと最短経路予測の手法を自己回帰世代として評価した。
  論文  参考訳（メタデータ） (2023-12-06T20:58:07Z)
• Offline Reinforcement Learning via Linear-Programming with Error-Bound Induced Constraints [26.008426384903764]
  オフライン強化学習(RL)は、事前に収集されたデータセットを使用して、マルコフ決定プロセス(MDP)の最適ポリシーを見つけることを目的としている。 本研究では,オフラインRLにおけるマルコフ決定過程の線形プログラミング (LP) の再検討を行う。
  論文  参考訳（メタデータ） (2022-12-28T15:28:12Z)
• Degeneracy is OK: Logarithmic Regret for Network Revenue Management with Indiscrete Distributions [13.310272407473809]
  我々は、従来のネットワーク収益管理(NRM)問題について、意思決定を受理/退避し、IIDの到着を$T$で検討する。 本モデルでは,O(log2 T)$ regret を実現するオンラインアルゴリズムを開発した。 2階成長の仮定を追加して、$O(log T)$ regretを達成する2番目の結果を得る。
  論文  参考訳（メタデータ） (2022-10-14T17:52:19Z)
• Model-free Learning of Regions of Attraction via Recurrent Sets [5.032993162348713]
  再帰性として知られる包摂性の概念をより緩和的に満たす集合を学習することを提案する。 穏やかな仮定の下では、安定平衡を含む $tau$-recurrent set がその ROA の部分集合でなければならないことを示す。 次に、この特性を利用して、再帰の反例を用いてROAの内部近似を計算するアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2022-04-21T19:03:17Z)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。 提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。 初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
  論文  参考訳（メタデータ） (2021-10-09T21:13:48Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。