論文の概要: Taming Wild Price Fluctuations: Monotone Stochastic Convex Optimization
with Bandit Feedback
- arxiv url: http://arxiv.org/abs/2103.09287v1
- Date: Tue, 16 Mar 2021 19:06:28 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-18 13:06:03.094473
- Title: Taming Wild Price Fluctuations: Monotone Stochastic Convex Optimization
with Bandit Feedback
- Title(参考訳): 乱暴な価格変動: バンディットフィードバックによる単調確率凸最適化
- Authors: Jad Salem, Swati Gupta, Vijay Kamble
- Abstract要約: 自動価格実験アルゴリズムによって生成される価格は、しばしば急激な変動を示す。
本稿では,価格系列の単調性制約下での需要学習を提案する。
我々のアルゴリズムは、単調な要求なしに最も達成可能な後悔率と同じ後悔率を保証している。
- 参考スコア(独自算出の注目度): 5.586191108738564
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Prices generated by automated price experimentation algorithms often display
wild fluctuations, leading to unfavorable customer perceptions and violations
of individual fairness: e.g., the price seen by a customer can be significantly
higher than what was seen by her predecessors, only to fall once again later.
To address this concern, we propose demand learning under a monotonicity
constraint on the sequence of prices, within the framework of stochastic convex
optimization with bandit feedback.
Our main contribution is the design of the first sublinear-regret algorithms
for monotonic price experimentation for smooth and strongly concave revenue
functions under noisy as well as noiseless bandit feedback. The monotonicity
constraint presents a unique challenge: since any increase (or decrease) in the
decision-levels is final, an algorithm needs to be cautious in its exploration
to avoid over-shooting the optimum. At the same time, minimizing regret
requires that progress be made towards the optimum at a sufficient pace.
Balancing these two goals is particularly challenging under noisy feedback,
where obtaining sufficiently accurate gradient estimates is expensive. Our key
innovation is to utilize conservative gradient estimates to adaptively tailor
the degree of caution to local gradient information, being aggressive far from
the optimum and being increasingly cautious as the prices approach the optimum.
Importantly, we show that our algorithms guarantee the same regret rates (up to
logarithmic factors) as the best achievable rates of regret without the
monotonicity requirement.
- Abstract(参考訳): 自動価格実験アルゴリズムによって生成される価格は、しばしば急激な変動を示し、好ましくない顧客の認識や個人の公正さの侵害につながる。
この問題に対処するため,帯域幅フィードバックを用いた確率凸最適化の枠組みにおいて,価格列の単調性制約の下で需要学習を提案する。
我々の主な貢献は、ノイズと無ノイズのバンディットフィードバックの下での滑らかで強い凹凸収益関数に対する単調価格実験のための最初のサブリニア・レグレットアルゴリズムの設計である。
決定レベルのいかなる増加(または減少)も最終的なものであるので、アルゴリズムは最適のオーバーシュートを避けるために、その探索において慎重でなければならない。
同時に、後悔を最小限に抑えるには、十分なペースで最適な方向に進む必要がある。
この2つの目標のバランスをとることは、ノイズの多いフィードバックの下では特に難しい。
我々の重要な革新は、保守的な勾配推定を利用して、局所的な勾配情報への注意度を適応的に調整し、最適から遠く離れ、価格が最適に近づくにつれて、より慎重になることです。
重要な点として,我々のアルゴリズムは,単調性の要件を伴わずに,最高の後悔率(対数的要因による)を保証できることを示した。
関連論文リスト
- Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and
Exp-Concave Games with Gradient Feedback [84.61895643083226]
オンライン勾配降下(OGD)は、強い凸性や単調性仮定の下では二重最適であることが知られている。
本稿では,これらのパラメータの事前知識を必要としない完全適応型OGDアルゴリズム,textsfAdaOGDを設計する。
論文 参考訳(メタデータ) (2023-10-21T18:38:13Z) - Distributionally Robust Optimization with Bias and Variance Reduction [9.341215359733601]
勾配に基づくアルゴリズムであるProspectは、スムーズな正規化損失に対する線形収束を享受していることを示す。
また、勾配法のようなベースラインよりも2~3$times$早く収束できることも示している。
論文 参考訳(メタデータ) (2023-10-21T00:03:54Z) - Rate-Optimal Policy Optimization for Linear Markov Decision Processes [71.65874793547107]
最安値の$widetilde O (sqrt K)$ regret, $K$はエピソード数を表す。
我々の研究は、バンディットフィードバックのある設定において最適な収束率(w.r.t.$K$)を確立する最初のものである。
現在、最適なレート保証を持つアルゴリズムは知られていない。
論文 参考訳(メタデータ) (2023-08-28T15:16:09Z) - Restarts subject to approximate sharpness: A parameter-free and optimal
scheme for first-order methods [2.513785998932353]
シャープネス(Sharpness)は、目的関数の準最適性によってミニマからの距離を束縛する連続最適化における仮定である。
シャープネスは、通常不明な問題固有の定数を伴い、以前の再起動スキームは収束率を減少させる。
対象関数の誤差に未知の定数摂動を組み込んだシャープネスの一般化である近似シャープネスの仮定を考察する。
論文 参考訳(メタデータ) (2023-01-05T19:01:41Z) - Autoregressive Bandits [58.46584210388307]
本稿では,オンライン学習環境であるAutoregressive Banditsを提案する。
報酬プロセスの軽微な仮定の下では、最適ポリシーを便利に計算できることが示される。
次に、新しい楽観的後悔最小化アルゴリズム、すなわちAutoRegressive Upper Confidence Bound (AR-UCB)を考案し、$widetildemathcalO left( frac(k+1)3/2sqrtnT (1-G)のサブ線形後悔を被る。
論文 参考訳(メタデータ) (2022-12-12T21:37:36Z) - Brownian Noise Reduction: Maximizing Privacy Subject to Accuracy
Constraints [53.01656650117495]
研究者と実践者の間には、プライバシとユーティリティのトレードオフの扱い方の違いがある。
ブラウン機構は、まず擬ブラウン運動の最終点に対応する高分散のガウス雑音を加えることで機能する。
我々は、古典的AboveThresholdアルゴリズムの一般化であるReduceedAboveThresholdでブラウン機構を補完する。
論文 参考訳(メタデータ) (2022-06-15T01:43:37Z) - Smoothed Online Convex Optimization Based on Discounted-Normal-Predictor [68.17855675511602]
円滑なオンライン凸最適化(SOCO)のためのオンライン予測戦略について検討する。
提案アルゴリズムは,各区間の切替コストで適応的後悔を最小限に抑えることができることを示す。
論文 参考訳(メタデータ) (2022-05-02T08:48:22Z) - High-probability Bounds for Non-Convex Stochastic Optimization with
Heavy Tails [55.561406656549686]
我々は、勾配推定が末尾を持つ可能性のある一階アルゴリズムを用いたヒルベルト非最適化を考える。
本研究では, 勾配, 運動量, 正規化勾配勾配の収束を高確率臨界点に収束させることと, 円滑な損失に対する最もよく知られた繰り返しを示す。
論文 参考訳(メタデータ) (2021-06-28T00:17:01Z) - Reward Biased Maximum Likelihood Estimation for Reinforcement Learning [13.820705458648233]
マルコフ連鎖の適応制御のためのRBMLE(Reward-Biased Maximum Likelihood Estimate)を提案した。
我々は、現在最先端のアルゴリズムと同様に、$mathcalO( log T)$が$T$の時間的水平線上で後悔していることを示します。
論文 参考訳(メタデータ) (2020-11-16T06:09:56Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。