論文の概要: 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つの目標のバランスをとることは、ノイズの多いフィードバックの下では特に難しい。
我々の重要な革新は、保守的な勾配推定を利用して、局所的な勾配情報への注意度を適応的に調整し、最適から遠く離れ、価格が最適に近づくにつれて、より慎重になることです。
重要な点として,我々のアルゴリズムは,単調性の要件を伴わずに,最高の後悔率(対数的要因による)を保証できることを示した。
関連論文リスト
- Optimizing Chance-Constrained Submodular Problems with Variable
Uncertainties [12.095075636344536]
本稿では,制約付き多種多様な問題を捕捉する,確率制約付き部分モジュラー最適化問題について検討する。
所与の最適解に対する定数近似比という,高品質な解を得ることのできるグリーディアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-09-23T04:48:49Z) - Adaptive Decision-Making with Constraints and Dependent Losses:
Performance Guarantees and Applications to Online and Nonlinear
Identification [5.787117733071415]
エージェントが有限の選択肢の中から繰り返し選択することで累積性能目標を最適化する適応的意思決定問題を考える。
我々のアルゴリズムと分析はインスタンス依存であり、つまり、環境の最適以下の選択は、我々の後悔の限界に利用され、反映される。
得られたアルゴリズムの性能は2つの数値例で強調される。
論文 参考訳（メタデータ） (2023-04-06T18:32:26Z) - Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement
Learning: Adaptivity and Computational Efficiency [90.40062452292091]
本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。
我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。
また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-02-21T00:17:24Z) - Learning to Optimize with Stochastic Dominance Constraints [103.26714928625582]
本稿では,不確実量を比較する問題に対して,単純かつ効率的なアプローチを開発する。
我々はラグランジアンの内部最適化をサロゲート近似の学習問題として再考した。
提案したライト-SDは、ファイナンスからサプライチェーン管理に至るまで、いくつかの代表的な問題において優れた性能を示す。
論文 参考訳（メタデータ） (2022-11-14T21:54:31Z) - A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
我々は,意思決定者が長期的制約の対象となる一連の意思決定をしなければならないオンライン学習問題について検討する。
目標は、全報酬を最大化し、同時に、$T$ラウンド全体で小さな累積違反を達成することである。
本稿では,この一般クラス問題に対して,未知のモデルに基づいて報酬と制約が選択された場合と,各ラウンドで敵が選択した場合の双方において,最良世界型アルゴリズムを提示する。
論文 参考訳（メタデータ） (2022-09-15T16:59:19Z) - Off-Policy Evaluation with Policy-Dependent Optimization Response [90.28758112893054]
我々は,テキスト政治に依存した線形最適化応答を用いた非政治評価のための新しいフレームワークを開発した。
摂動法による政策依存推定のための非バイアス推定器を構築する。
因果介入を最適化するための一般的なアルゴリズムを提供する。
論文 参考訳（メタデータ） (2022-02-25T20:25:37Z) - Safe Online Bid Optimization with Return-On-Investment and Budget
Constraints subject to Uncertainty [87.81197574939355]
最適化問題と学習問題の両方について検討する。
我々は、潜在的に線形な数の制約違反を犠牲にして、サブ線形後悔を保証するアルゴリズム、すなわちGCBを提供する。
より興味深いことに、我々はGCB_safe(psi,phi)というアルゴリズムを提供し、サブ線形擬似回帰と安全性w.h.p.の両方を、耐性 psi と phi を受け入れるコストで保証する。
論文 参考訳（メタデータ） (2022-01-18T17:24:20Z) - Fair Incentives for Repeated Engagement [0.46040036610482665]
我々は、参加決定が受け取ったインセンティブに依存するエージェントに直面する場合、維持のための最適な金融インセンティブスキームを見つけるという課題について検討する。
明示的な差別がなくても、システムの種類構成を変化させることで、ポリシーが無意識に異なるタイプのエージェントを識別できることが示される。
論文 参考訳（メタデータ） (2021-10-28T04:13:53Z) - Concave Utility Reinforcement Learning with Zero-Constraint Violations [43.29210413964558]
本稿では,凸制約を伴うCURL(Concave utility reinforcement Learning)の問題点について考察する。
制約違反をゼロにするモデルベース学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-09-12T06:13:33Z) - On the Optimality of Batch Policy Optimization Algorithms [106.89498352537682]
バッチポリシー最適化は、環境と対話する前に既存のデータをポリシー構築に活用することを検討する。
信頼調整インデックスアルゴリズムは楽観的,悲観的,中立的いずれであってもミニマックス最適であることを示す。
最適値予測の本来の難易度を考慮した新しい重み付き最小値基準を提案する。
論文 参考訳（メタデータ） (2021-04-06T05:23:20Z) - Regularized Online Allocation Problems: Fairness and Beyond [7.433931244705934]
本稿では, 総資源消費に作用する非線形正規化器を含む変種である, 語彙化オンライン割当問題を紹介する。
この問題では、要求は時間とともに繰り返し届き、各要求に対して、意思決定者は報酬を生成しリソースを消費するアクションを取る必要があります。
目的は、資源制約を受ける加算可分な報酬と非分離可正則化器の値とを同時に最大化することである。
論文 参考訳（メタデータ） (2020-07-01T14:24:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。