論文の概要: Constant Regret Re-solving Heuristics for Price-based Revenue Management
- arxiv url: http://arxiv.org/abs/2009.02861v2
- Date: Tue, 29 Dec 2020 20:01:20 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-21 03:14:11.753024
- Title: Constant Regret Re-solving Heuristics for Price-based Revenue Management
- Title(参考訳): 物価ベースの収益管理のための定期的レグレト・リゾルディング・ヒューリスティックス
- Authors: Yining Wang and He Wang
- Abstract要約: 最適政策の値と比較して, 自然解決はO(1)$後悔となることを示す。
また、最適ポリシーの値と流体モデルの値の間には$Omega(ln T)$ギャップがあることも証明する。
- 参考スコア(独自算出の注目度): 17.344365325417602
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Price-based revenue management is an important problem in operations
management with many practical applications. The problem considers a retailer
who sells a product (or multiple products) over $T$ consecutive time periods
and is subject to constraints on the initial inventory levels. While the
optimal pricing policy could be obtained via dynamic programming, such an
approach is sometimes undesirable because of high computational costs.
Approximate policies, such as the re-solving heuristics, are often applied as
computationally tractable alternatives. In this paper, we show the following
two results. First, we prove that a natural re-solving heuristic attains $O(1)$
regret compared to the value of the optimal policy. This improves the $O(\ln
T)$ regret upper bound established in the prior work of
\cite{jasin2014reoptimization}. Second, we prove that there is an $\Omega(\ln
T)$ gap between the value of the optimal policy and that of the fluid model.
This complements our upper bound result by showing that the fluid is not an
adequate information-relaxed benchmark when analyzing price-based revenue
management algorithms.
- Abstract(参考訳): 価格ベースの収益管理は多くの実践的な応用で運用管理において重要な問題である。
問題は、商品(または複数の製品)を連続してt$の期間にわたって販売し、初期の在庫水準に制約を受ける小売業者を考えることである。
最適価格ポリシーは動的プログラミングによって得ることができるが、高い計算コストのためにそのようなアプローチは望ましくない場合もある。
再解決ヒューリスティックスのような近似ポリシーは、しばしば計算的に抽出可能な代替手段として適用される。
本稿では,以下の2つの結果を示す。
まず, 自然再解法ヒューリスティックは, 最適方針の値と比較して, $o(1)$ regret が得られることを証明した。
これは \cite{jasin2014reoptimization} の以前の研究で確立された $O(\ln T)$ regret上界を改善する。
第二に、最適ポリシーの値と流体モデルの値の間には$\Omega(\ln T)$ギャップがあることが証明される。
これは、価格ベースの収益管理アルゴリズムを分析する際に、流体が適切な情報関連ベンチマークではないことを示すことで、上界の結果を補完する。
関連論文リスト
- 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) - Provably Efficient Reinforcement Learning via Surprise Bound [66.15308700413814]
本稿では,一般値関数近似を用いた効率の良い強化学習アルゴリズムを提案する。
本アルゴリズムは, 線形設定と疎高次元線形設定の両方に適用した場合に, 合理的な後悔境界を達成できる。
論文 参考訳(メタデータ) (2023-02-22T20:21:25Z) - Estimating Optimal Policy Value in General Linear Contextual Bandits [50.008542459050155]
多くのバンドイット問題において、政策によって達成可能な最大報酬は、前もって不明であることが多い。
我々は,最適政策が学習される前に,サブ線形データ構造における最適政策値を推定する問題を考察する。
V*$で問題依存上界を推定する,より実用的で効率的なアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-02-19T01:09:24Z) - Best of Both Worlds Policy Optimization [33.13041034490332]
本稿では,正則化器,探索ボーナス,学習率を適切に設計することにより,損失が相反する場合には,より好意的なポリログ$(T)=後悔が得られることを示す。
政策最適化のために、ギャップ依存のポリログ$(T)$後悔境界が示されるのはこれが初めてである。
論文 参考訳(メタデータ) (2023-02-18T19:46:11Z) - 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) - Efficient Policy Iteration for Robust Markov Decision Processes via
Regularization [49.05403412954533]
ロバストな意思決定プロセス(MDP)は、システムのダイナミクスが変化している、あるいは部分的にしか知られていない決定問題をモデル化するためのフレームワークを提供する。
最近の研究は、長方形長方形の$L_p$頑健なMDPと正規化されたMDPの等価性を確立し、標準MDPと同じレベルの効率を享受する規則化されたポリシー反復スキームを導出した。
本研究では、政策改善のステップに焦点をあて、欲求政策と最適なロバストなベルマン作用素のための具体的な形式を導出する。
論文 参考訳(メタデータ) (2022-05-28T04:05:20Z) - Restless Bandits with Many Arms: Beating the Central Limit Theorem [25.639496138046546]
有限ホライズン・レスト・ブレイディット(有限ホライズン・レスト・ブレイディット)は、レコメンデーターシステム、アクティブラーニング、収益管理、その他多くの分野で重要な役割を果たしている。
最適ポリシーは、原理的には動的プログラミングを用いて計算できるが、計算に必要なスケールは腕数$N$で指数関数的にスケールする。
最適性ギャップが$O(1)$である流体プライオリティポリシと呼ばれる、非退化条件と、実用的に計算可能な新しいポリシーのクラスを特徴付ける。
論文 参考訳(メタデータ) (2021-07-25T23:27:12Z) - Improved Regret Bound and Experience Replay in Regularized Policy
Iteration [22.621710838468097]
無限ホライゾンマルコフ決定過程(mdps)における学習アルゴリズムを関数近似を用いて検討する。
まず、ほぼ同一の仮定の下で、Politexアルゴリズムの後悔解析を$O(T3/4)$から$O(sqrtT)$にシャープできることを示す。
その結果、計算効率の良いアルゴリズムに対して、最初の高い確率の$o(sqrtt)$ regretバウンドが得られる。
論文 参考訳(メタデータ) (2021-02-25T00:55:07Z) - Logarithmic Regret in Feature-based Dynamic Pricing [0.0]
機能ベースの動的価格設定は、差別化された製品の価格設定の人気が高まっているモデルです。
我々は、インフラクティゲンと敵対的な特徴設定のための2つのアルゴリズムを提供し、両方の最適$O(dlogT)$後悔境界を証明します。
さらに、より一般的な設定で$(sqrtt)$情報理論下限を証明し、"需要曲線の知識"が機能ベースの動的価格の指数関数的な改善につながることを実証します。
論文 参考訳(メタデータ) (2021-02-20T00:45:33Z) - Online Apprenticeship Learning [58.45089581278177]
見習い学習(AL)では、コスト関数にアクセスせずにマルコフ決定プロセス(MDP)が与えられます。
目標は、事前に定義されたコスト関数のセットで専門家のパフォーマンスに一致するポリシーを見つけることです。
ミラー下降型ノンレグレットアルゴリズムを2つ組み合わせることで,OAL問題を効果的に解くことができることを示す。
論文 参考訳(メタデータ) (2021-02-13T12:57:51Z) - Efficient Optimistic Exploration in Linear-Quadratic Regulators via
Lagrangian Relaxation [107.06364966905821]
線形2次レギュレータ(LQR)設定における探索・探索ジレンマについて検討した。
有限 MDP に対する楽観的アルゴリズムで用いられる拡張値反復アルゴリズムに着想を得て,Oulq の楽観的最適化を緩和することを提案する。
我々は、少なくとも$Obig(log (1/epsilon)big)$ Riccati方程式を解くことで、$epsilon$-OptimisticControllerを効率的に計算できることを示した。
論文 参考訳(メタデータ) (2020-07-13T16:30:47Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。