論文の概要: Demand Balancing in Primal-Dual Optimization for Blind Network Revenue Management
- arxiv url: http://arxiv.org/abs/2404.04467v1
- Date: Sat, 6 Apr 2024 01:39:51 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-09 21:08:32.788809
- Title: Demand Balancing in Primal-Dual Optimization for Blind Network Revenue Management
- Title（参考訳）: ブラインドネットワーク収益管理のためのプライマルダイアル最適化における需要バランス
- Authors: Sentao Miao, Yining Wang,
- Abstract要約: 本稿では,従来のネットワーク収益管理問題を未知の非パラメトリック要求で解決する,最適理論的後悔を伴う実用的なアルゴリズムを提案する。
重要な技術的貢献は、いわゆる需要バランスであり、これは資源在庫の制約に対する欠陥の違反を相殺するために、各期間に一次解(すなわち価格)を他の価格と組み合わせるものである。
- 参考スコア（独自算出の注目度）: 6.72809363581332
- License: http://creativecommons.org/publicdomain/zero/1.0/
- Abstract: This paper proposes a practically efficient algorithm with optimal theoretical regret which solves the classical network revenue management (NRM) problem with unknown, nonparametric demand. Over a time horizon of length $T$, in each time period the retailer needs to decide prices of $N$ types of products which are produced based on $M$ types of resources with unreplenishable initial inventory. When demand is nonparametric with some mild assumptions, Miao and Wang (2021) is the first paper which proposes an algorithm with $O(\text{poly}(N,M,\ln(T))\sqrt{T})$ type of regret (in particular, $\tilde O(N^{3.5}\sqrt{T})$ plus additional high-order terms that are $o(\sqrt{T})$ with sufficiently large $T\gg N$). In this paper, we improve the previous result by proposing a primal-dual optimization algorithm which is not only more practical, but also with an improved regret of $\tilde O(N^{3.25}\sqrt{T})$ free from additional high-order terms. A key technical contribution of the proposed algorithm is the so-called demand balancing, which pairs the primal solution (i.e., the price) in each time period with another price to offset the violation of complementary slackness on resource inventory constraints. Numerical experiments compared with several benchmark algorithms further illustrate the effectiveness of our algorithm.
- Abstract（参考訳）: 本稿では,従来のネットワーク収益管理問題(NRM)を未知の非パラメトリック要求で解決する,最適理論的後悔を伴う実用的なアルゴリズムを提案する。
期間毎に、小売業者は、要求できない初期在庫を持つM$タイプのリソースに基づいて生産されるN$タイプの商品の価格を決定する必要がある。
需要がある程度の仮定で非パラメトリックな場合、Miao and Wang (2021) は$O(\text{poly}(N,M,\ln(T))\sqrt{T})$ 後悔のタイプ(特に $\tilde O(N^{3.5}\sqrt{T})$ と $o(\sqrt{T})$ の高次項を十分に大きい$T\gg N$ で提案する最初の論文である。
本稿では,より実用的であるだけでなく,高次項を含まない$\tilde O(N^{3.25}\sqrt{T})$を改良した原始双対最適化アルゴリズムを提案する。
提案アルゴリズムの主な技術的貢献はいわゆる需要バランスであり、これは資源在庫の制約に対する相補的欠陥の違反を相殺するために、各期間に一次解(すなわち価格)を他の価格と組み合わせるものである。
いくつかのベンチマークアルゴリズムと比較した数値実験により,提案アルゴリズムの有効性がさらに示された。
関連論文リスト
- Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。
まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。
我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
論文 参考訳（メタデータ） (2024-06-07T12:07:16Z) - Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
一般化線形モデル (GLM) フレームワークを用いて, citelu2021low で提案した一般化低ランク行列帯域問題について検討する。
既存のアルゴリズムの計算不可能性と理論的制約を克服するため,まずG-ESTTフレームワークを提案する。
G-ESTT は $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret を達成でき、G-ESTS は $tildeO を達成できることを示す。
論文 参考訳（メタデータ） (2024-01-14T14:14:19Z) - Settling the Sample Complexity of Online Reinforcement Learning [92.02082223856479]
バーンインコストを発生させることなく、最小限の最適後悔を実現する方法を示す。
最適値/コストや一定の分散といった問題依存量の影響を明らかにするために、我々の理論を拡張します。
論文 参考訳（メタデータ） (2023-07-25T15:42:11Z) - Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。
本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-30T14:37:21Z) - Learning to Order for Inventory Systems with Lost Sales and Uncertain
Supplies [21.690446677016247]
我々は, 在庫管理システムを, 計画的地平線上でのリードタイム$L$とみなし, 供給は不確実であり, 注文量の関数である。
提案アルゴリズムは,O(L+sqrtT)$が$Lgeqlog(T)$である場合に,そのアルゴリズムのコストと,O(L+sqrtT)$に対する最適ポリシーとの相違(英語版)を生じることを示す。
論文 参考訳（メタデータ） (2022-07-10T22:11:32Z) - Human-in-the-loop: Provably Efficient Preference-based Reinforcement
Learning with General Function Approximation [107.54516740713969]
本研究は,RL(Human-in-the-loop reinforcement learning)を軌道的嗜好で検討する。
各ステップで数値的な報酬を受ける代わりに、エージェントは人間の監督者から軌道上のペアよりも優先される。
一般関数近似を用いたPbRLの楽観的モデルベースアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-05-23T09:03:24Z) - An Accelerated Stochastic Algorithm for Solving the Optimal Transport
Problem [2.1485350418225244]
線形制約付き最適化問題を解くために,分散低減アルゴリズム (PDASGD) を用いた一次2次元加速勾配降下法を提案する。
PDASGDは最もよく知られた計算複雑性を享受しており、$widetildemathcalO(n2/epsilon)$、$n$は原子の数、$epsilon>0$は精度である。
論文 参考訳（メタデータ） (2022-03-02T01:16:10Z) - Online Allocation with Two-sided Resource Constraints [44.5635910908944]
我々は,要求が順次到着する,リソース制約の低いオンラインアロケーション問題を考える。
提案手法では, リクエスト全体を知るオフライン問題に対して, 1-O (fracepsilonalpha-epsilon)$-competitive ratioを求めるアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-12-28T02:21:06Z) - 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) - Constant Regret Re-solving Heuristics for Price-based Revenue Management [17.344365325417602]
最適政策の値と比較して, 自然解決はO(1)$後悔となることを示す。
また、最適ポリシーの値と流体モデルの値の間には$Omega(ln T)$ギャップがあることも証明する。
論文 参考訳（メタデータ） (2020-09-07T02:28:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。