論文の概要: Learning to Order for Inventory Systems with Lost Sales and Uncertain Supplies

• arxiv url: http://arxiv.org/abs/2207.04550v3
• Date: Mon, 22 May 2023 18:52:52 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-25 01:40:49.099205
• Title: Learning to Order for Inventory Systems with Lost Sales and Uncertain Supplies
• Title（参考訳）: 損失販売と不確実な供給を伴う在庫システムの発注の学習
• Authors: Boxiao Chen, Jiashuo Jiang, Jiawei Zhang and Zhengyuan Zhou
• Abstract要約: 我々は, 在庫管理システムを, 計画的地平線上でのリードタイム$L$とみなし, 供給は不確実であり, 注文量の関数である。 提案アルゴリズムは,O(L+sqrtT)$が$Lgeqlog(T)$である場合に,そのアルゴリズムのコストと,O(L+sqrtT)$に対する最適ポリシーとの相違(英語版)を生じることを示す。
• 参考スコア（独自算出の注目度）: 21.37791303845928
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider a stochastic lost-sales inventory control system with a lead time $L$ over a planning horizon $T$. Supply is uncertain, and is a function of the order quantity (due to random yield/capacity, etc). We aim to minimize the $T$-period cost, a problem that is known to be computationally intractable even under known distributions of demand and supply. In this paper, we assume that both the demand and supply distributions are unknown and develop a computationally efficient online learning algorithm. We show that our algorithm achieves a regret (i.e. the performance gap between the cost of our algorithm and that of an optimal policy over $T$ periods) of $O(L+\sqrt{T})$ when $L\geq\log(T)$. We do so by 1) showing our algorithm cost is higher by at most $O(L+\sqrt{T})$ for any $L\geq 0$ compared to an optimal constant-order policy under complete information (a well-known and widely-used algorithm) and 2) leveraging its known performance guarantee from the existing literature. To the best of our knowledge, a finite-sample $O(\sqrt{T})$ (and polynomial in $L$) regret bound when benchmarked against an optimal policy is not known before in the online inventory control literature. A key challenge in this learning problem is that both demand and supply data can be censored; hence only truncated values are observable. We circumvent this challenge by showing that the data generated under an order quantity $q^2$ allows us to simulate the performance of not only $q^2$ but also $q^1$ for all $q^1<q^2$, a key observation to obtain sufficient information even under data censoring. By establishing a high probability coupling argument, we are able to evaluate and compare the performance of different order policies at their steady state within a finite time horizon. Since the problem lacks convexity, we develop an active elimination method that adaptively rules out suboptimal solutions.
• Abstract（参考訳）: 計画的地平線上でのリードタイムが$L$である確率的ロスセール在庫管理システムを考察する。 供給は不確実であり、(ランダムな収量/容量などによる)順序量の関数である。 私たちは、需要と供給の既知の分布下でも計算が難しい問題であるt$周期コストを最小化することを目指している。 本稿では,需要分布と供給分布の両方が未知であると仮定し,計算効率の高いオンライン学習アルゴリズムを開発した。 提案アルゴリズムは,O(L+\sqrt{T})$が$L\geq\log(T)$である場合に,そのアルゴリズムのコストと,O(L+\sqrt{T})$に対する最適ポリシーとの相違(英語版)を生じることを示す。 私たちはそうします 1) 完全情報(よく知られ、広く使われているアルゴリズム)に基づく最適定数順序ポリシーと比較して、任意の$l\geq 0$に対して最大$o(l+\sqrt{t})$でアルゴリズムコストを示す。 2) 既知の性能保証を既存文献から活用すること。 私たちの知る限りでは、オンライン在庫管理の文献では、最適なポリシーに対してベンチマークを行った場合、有限サンプルの$o(\sqrt{t})$(および$l$の多項式)が制限される。 この学習問題の鍵となる課題は、需要データと供給データの両方が検閲可能であることである。 注文量$q^2$の下で生成されたデータは、すべての$q^1<q^2$に対して$q^1$のパフォーマンスをシミュレートできることを示すことにより、この課題を回避する。 高確率カップリングの議論を確立することで、有限時間地平線内の定常状態における異なる順序ポリシーの性能を評価し、比較することができる。 この問題には凸性が欠けているため,亜最適解を適応的に排除する能動除去法を開発した。

関連論文リスト

• Demand Balancing in Primal-Dual Optimization for Blind Network Revenue Management [6.72809363581332]
  本稿では,従来のネットワーク収益管理問題を未知の非パラメトリック要求で解決する,最適理論的後悔を伴う実用的なアルゴリズムを提案する。 重要な技術的貢献は、いわゆる需要バランスであり、これは資源在庫の制約に対する欠陥の違反を相殺するために、各期間に一次解(すなわち価格)を他の価格と組み合わせるものである。
  論文  参考訳（メタデータ） (2024-04-06T01:39:51Z)
• Best-of-Both-Worlds Algorithms for Linear Contextual Bandits [11.94312915280916]
  両世界のベスト・オブ・ワールドズ・アルゴリズムを$K$武器付き線形文脈包帯に対して検討する。 我々のアルゴリズムは、敵対的体制と敵対的体制の両方において、ほぼ最適の後悔の限界を提供する。
  論文  参考訳（メタデータ） (2023-12-24T08:27:30Z)
• A Doubly Robust Approach to Sparse Reinforcement Learning [19.68978899041642]
  エピソードスパークリニアマルコフ決定過程(SMDP)に対する新しい後悔アルゴリズムを提案する。 提案アルゴリズムは$tildeO(sigma-1_min s_star H sqrtN)$である。
  論文  参考訳（メタデータ） (2023-10-23T18:52:17Z)
• Model-Free, Regret-Optimal Best Policy Identification in Online CMDPs [17.62509045102346]
  本稿では,CMDP(Constrained Markov Decision Processs)における最適ポリシー識別問題について考察する。 私たちは、モデルフリーで、後悔の少ないアルゴリズムに興味を持ち、確率の高いほぼ最適なポリシーを特定しています。 オンラインCMDPのサブ線形後悔と制約違反を伴う既存のモデルフリーアルゴリズムでは、最適ポリシーに対する収束保証は提供されない。
  論文  参考訳（メタデータ） (2023-09-27T04:33:09Z)
• Settling the Sample Complexity of Online Reinforcement Learning [92.02082223856479]
  バーンインコストを発生させることなく、最小限の最適後悔を実現する方法を示す。 最適値/コストや一定の分散といった問題依存量の影響を明らかにするために、我々の理論を拡張します。
  論文  参考訳（メタデータ） (2023-07-25T15:42:11Z)
• Estimating Optimal Policy Value in General Linear Contextual Bandits [50.008542459050155]
  多くのバンドイット問題において、政策によって達成可能な最大報酬は、前もって不明であることが多い。 我々は,最適政策が学習される前に,サブ線形データ構造における最適政策値を推定する問題を考察する。 V*$で問題依存上界を推定する,より実用的で効率的なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-19T01:09:24Z)
• Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Path [106.37656068276902]
  本稿では,最短経路(SSP)問題において,$epsilon$-optimal Policyを学習する際のサンプル複雑性について検討する。 学習者が生成モデルにアクセスできる場合、複雑性境界を導出する。 我々は、$S$状態、$A$アクション、最小コスト$c_min$、およびすべての状態に対する最適ポリシーの最大期待コストを持つ最悪のSSPインスタンスが存在することを示す。
  論文  参考訳（メタデータ） (2022-10-10T18:34:32Z)
• Nearly Optimal Policy Optimization with Stable at Any Time Guarantee [53.155554415415445]
  citetshani 2020optimisticのポリシーベースのメソッドは、$tildeO(sqrtSAH3K + sqrtAH4K)$である。$S$は状態の数、$A$はアクションの数、$H$は地平線、$K$はエピソードの数、$sqrtSH$は情報理論の下限の$tildeOmega(sqrtSAH)と比べてギャップがある。
  論文  参考訳（メタデータ） (2021-12-21T01:54:17Z)
• List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
  高次元におけるリストデコタブル平均推定の基本的な課題について検討する。 我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。 我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
  論文  参考訳（メタデータ） (2020-11-19T17:21:37Z)
• Naive Exploration is Optimal for Online LQR [49.681825576239355]
  最適後悔尺度は$widetildeTheta(sqrtd_mathbfu2 d_mathbfx T)$で、$T$は時間ステップの数、$d_mathbfu$は入力空間の次元、$d_mathbfx$はシステム状態の次元である。 我々の下界は、かつての$mathrmpoly(logT)$-regretアルゴリズムの可能性を排除する。
  論文  参考訳（メタデータ） (2020-01-27T03:44:54Z)

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

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