論文の概要: Safe Online Bid Optimization with Return-On-Investment and Budget Constraints subject to Uncertainty

• arxiv url: http://arxiv.org/abs/2201.07139v1
• Date: Tue, 18 Jan 2022 17:24:20 GMT
• ステータス: 処理完了
• システム内更新日: 2022-01-19 14:03:30.963063
• Title: Safe Online Bid Optimization with Return-On-Investment and Budget Constraints subject to Uncertainty
• Title（参考訳）: 不確実性を考慮したリターンオン投資と予算制約による安全なオンライン入札最適化
• Authors: Matteo Castiglioni, Alessandro Nuara, Giulia Romano, Giorgio Spadaro, Francesco Trov\`o, Nicola Gatti
• Abstract要約: 最適化問題と学習問題の両方について検討する。 我々は、潜在的に線形な数の制約違反を犠牲にして、サブ線形後悔を保証するアルゴリズム、すなわちGCBを提供する。 より興味深いことに、我々はGCB_safe(psi,phi)というアルゴリズムを提供し、サブ線形擬似回帰と安全性w.h.p.の両方を、耐性 psi と phi を受け入れるコストで保証する。
• 参考スコア（独自算出の注目度）: 87.81197574939355
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In online marketing, the advertisers' goal is usually a tradeoff between achieving high volumes and high profitability. The companies' business units customarily address this tradeoff by maximizing the volumes while guaranteeing a lower bound to the Return On Investment (ROI). This paper investigates combinatorial bandit algorithms for the bid optimization of advertising campaigns subject to uncertain budget and ROI constraints. We study the nature of both the optimization and learning problems. In particular, when focusing on the optimization problem without uncertainty, we show that it is inapproximable within any factor unless P=NP, and we provide a pseudo-polynomial-time algorithm that achieves an optimal solution. When considering uncertainty, we prove that no online learning algorithm can violate the (ROI or budget) constraints during the learning process a sublinear number of times while guaranteeing a sublinear pseudo-regret. Thus, we provide an algorithm, namely GCB, guaranteeing sublinear regret at the cost of a potentially linear number of constraints violations. We also design its safe version, namely GCB_{safe}, guaranteeing w.h.p. a constant upper bound on the number of constraints violations at the cost of a linear pseudo-regret. More interestingly, we provide an algorithm, namely GCB_{safe}(\psi,\phi), guaranteeing both sublinear pseudo-regret and safety w.h.p. at the cost of accepting tolerances \psi and \phi in the satisfaction of the ROI and budget constraints, respectively. This algorithm actually mitigates the risks due to the constraints violations without precluding the convergence to the optimal solution. Finally, we experimentally compare our algorithms in terms of pseudo-regret/constraint-violation tradeoff in settings generated from real-world data, showing the importance of adopting safety constraints in practice and the effectiveness of our algorithms.
• Abstract（参考訳）: オンラインマーケティングでは、広告主のゴールは通常、高いボリュームと高い利益率のトレードオフである。 両社のビジネスユニットはこのトレードオフに対して、投資収益率(ROI)の低下を保証しつつ、ボリュームを最大化することで、慣習的に対処する。 本稿では,不確定な予算とroi制約を受ける広告キャンペーンの入札最適化のための組合せバンディットアルゴリズムについて検討する。 我々は最適化問題と学習問題の両方の性質について研究する。 特に、不確実性のない最適化問題に注目する場合、P=NPを除いた任意の係数で近似できないことを示し、最適解を得る擬似多項式時間アルゴリズムを提供する。 不確実性を考慮すると、オンライン学習アルゴリズムが学習過程の制約(ROIまたは予算)に何回も違反することはなく、サブ線形擬似回帰を保証する。 そこで本研究では, 線形な制約違反のコストを犠牲にして, サブリニアな後悔を保証できるアルゴリズム, gcbを提案する。 我々はまた、その安全なバージョン、すなわちGCB_{safe}を設計し、線形擬似回帰のコストで制約違反の数に一定の上限を保証します。 より興味深いことに、我々は、それぞれROIと予算制約の満足度において許容度 \psi と \phi を受け入れるコストで、サブ線形擬似回帰と安全性 w.h.p. の両方を保証するアルゴリズム、GCB_{safe}(\psi,\phi) を提供する。 このアルゴリズムは、最適解への収束を排除せずに、制約違反によるリスクを軽減する。 最後に,実世界データから生成された設定における疑似レグレット/コンストラクション違反トレードオフの観点から,本アルゴリズムを実験的に比較し,安全性制約を実際に採用することの重要性とアルゴリズムの有効性を示した。

関連論文リスト

• Best-of-Both-Worlds Policy Optimization for CMDPs with Bandit Feedback [34.7178680288326]
  Stradi et al.(2024) は、マルコフ決定過程に制約のある最初のベスト・オブ・ボス・ワールドズ・アルゴリズムを提案した。 本稿では,CMDPにおける帯域幅フィードバックを用いたベスト・オブ・ワールドズ・アルゴリズムを提案する。 本アルゴリズムは政策最適化手法に基づいており, 占有率に基づく手法よりも効率的である。
  論文  参考訳（メタデータ） (2024-10-03T07:44:40Z)
• Learning Constrained Markov Decision Processes With Non-stationary Rewards and Constraints [34.7178680288326]
  制約付きマルコフ決定プロセス(CMDP)では、逆の報酬と制約があり、よく知られた不合理性の結果、任意のアルゴリズムがサブリニア後悔とサブリニア制約違反を達成できない。 非定常的な報酬や制約のあるCMDPでは、非定常性の増加とともに性能がスムーズに低下するアルゴリズムを提供することで、この負の結果が緩和できることが示される。
  論文  参考訳（メタデータ） (2024-05-23T09:48:48Z)
• LinearAPT: An Adaptive Algorithm for the Fixed-Budget Thresholding Linear Bandit Problem [4.666048091337632]
  本稿では、Thresholding Linear Bandit(TLB)問題の固定予算設定のために設計された新しいアルゴリズムであるLinearAPTを提案する。 コントリビューションでは、LinearAPTの適応性、単純性、計算効率を強調しており、複雑なシーケンシャルな意思決定課題に対処するためのツールキットとして貴重なものとなっている。
  論文  参考訳（メタデータ） (2024-03-10T15:01:50Z)
• 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)
• Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear Contextual Bandits and Markov Decision Processes [59.61248760134937]
  本稿では,$tildeO(sqrtT+zeta)$を後悔するアルゴリズムを提案する。 提案アルゴリズムは、最近開発された線形文脈帯域からの不確実性重み付き最小二乗回帰に依存する。 本稿では,提案アルゴリズムをエピソディックなMDP設定に一般化し,まず汚職レベル$zeta$への付加的依存を実現する。
  論文  参考訳（メタデータ） (2022-12-12T15:04:56Z)
• A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
  我々は,意思決定者が長期的制約の対象となる一連の意思決定をしなければならないオンライン学習問題について検討する。 目標は、全報酬を最大化し、同時に、$T$ラウンド全体で小さな累積違反を達成することである。 本稿では,この一般クラス問題に対して,未知のモデルに基づいて報酬と制約が選択された場合と,各ラウンドで敵が選択した場合の双方において,最良世界型アルゴリズムを提示する。
  論文  参考訳（メタデータ） (2022-09-15T16:59:19Z)
• Log Barriers for Safe Black-box Optimization with Application to Safe Reinforcement Learning [72.97229770329214]
  本稿では,学習時の安全性維持が不可欠である高次元非線形最適化問題に対する一般的なアプローチを提案する。 LBSGDと呼ばれるアプローチは、慎重に選択されたステップサイズで対数障壁近似を適用することに基づいている。 安全強化学習における政策課題の違反を最小限に抑えるためのアプローチの有効性を実証する。
  論文  参考訳（メタデータ） (2022-07-21T11:14:47Z)
• Safe Online Convex Optimization with Unknown Linear Safety Constraints [0.0]
  安全なオンライン凸最適化の問題について検討し、各ステップの動作は一連の線形安全制約を満たす必要がある。 線形安全性制約を指定するパラメータはアルゴリズムでは未知である。 安全なベースライン動作が可能であるという仮定の下で、SO-PGDアルゴリズムは、後悔する$O(T2/3)$を達成していることを示す。
  論文  参考訳（メタデータ） (2021-11-14T19:49:19Z)
• Concave Utility Reinforcement Learning with Zero-Constraint Violations [43.29210413964558]
  本稿では,凸制約を伴うCURL(Concave utility reinforcement Learning)の問題点について考察する。 制約違反をゼロにするモデルベース学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-12T06:13:33Z)
• Large-Scale Methods for Distributionally Robust Optimization [53.98643772533416]
  我々のアルゴリズムは、トレーニングセットのサイズとパラメータの数によらず、多くの評価勾配を必要とすることを証明している。 MNIST と ImageNet の実験により,本手法の 9-36 倍の効率性を持つアルゴリズムの理論的スケーリングが確認された。
  論文  参考訳（メタデータ） (2020-10-12T17:41:44Z)

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

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