論文の概要: Online Learning under Budget and ROI Constraints and Applications to
Bidding in Non-Truthful Auctions
- arxiv url: http://arxiv.org/abs/2302.01203v2
- Date: Thu, 25 May 2023 10:56:53 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-26 22:48:23.332407
- Title: Online Learning under Budget and ROI Constraints and Applications to
Bidding in Non-Truthful Auctions
- Title（参考訳）: 予算・ROI制約下におけるオンライン学習と非実効入札への活用
- Authors: Matteo Castiglioni, Andrea Celli, Christian Kroer
- Abstract要約: 意思決定者がコストのかかる意思決定をしなければならないオンライン学習問題について検討する。
実践的妥当性の様々なメカニズムにおいて最適な入札を行うためのフレームワークのインスタンス化方法を示す。
- 参考スコア（独自算出の注目度）: 54.28273783164608
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study online learning problems in which a decision maker has to make a
sequence of costly decisions, with the goal of maximizing their expected reward
while adhering to budget and return-on-investment (ROI) constraints. Previous
work requires the decision maker to know beforehand some specific parameters
related to the degree of strict feasibility of the offline problem. Moreover,
when inputs are adversarial, it requires the existence of a strictly feasible
solution to the offline optimization problem at each round. Both requirements
are unrealistic for practical applications such as bidding in online ad
auctions. We propose a best-of-both-worlds primal-dual framework which
circumvents both assumptions by exploiting the notion of interval regret,
providing guarantees under both stochastic and adversarial inputs. Our proof
techniques can be applied to both input models with minimal modifications,
thereby providing a unified perspective on the two problems. Finally, we show
how to instantiate the framework to optimally bid in various mechanisms of
practical relevance, such as first- and second-price auctions.
- Abstract（参考訳）: 我々は、予算と投資リターン(roi)の制約に固執しながら、期待する報酬を最大化することを目的として、意思決定者が一連のコストのかかる意思決定をしなければならないオンライン学習問題を研究する。
以前の作業では、オフライン問題の厳密な実現可能性の度合いに関連する特定のパラメータを事前に知る必要がある。
さらに、入力が逆ならば、各ラウンドにおけるオフライン最適化問題の厳密な解決方法が存在する必要がある。
どちらの要件も、オンライン広告オークションの入札のような実用的な応用には非現実的である。
本稿では,相互後悔の概念を生かして両者の仮定を回避し,確率的入力と逆入力の両方で保証する最善の両世界の原始双対的枠組みを提案する。
提案手法は,両入力モデルに最小限の修正で適用可能であり,この2つの問題に対する統一的な視点を提供する。
最後に、第1および第2価格オークションのような実用的妥当性の様々なメカニズムを最適に入札するためのフレームワークのインスタンス化方法を示す。
関連論文リスト
- Selling Joint Ads: A Regret Minimization Perspective [7.288063443108292]
オンライン小売によるモチベーションにより、一品(広告スロットなど)を2つの非排除購入者(商店、ブランド等)に販売する問題を考える。
この問題は、例えば、マーチャントとブランドが商品を宣伝するために競売に協力して入札する状況と、表示されている広告の恩恵を捉えている。
メカニズムは2つの入札を収集し、どちらを割り当てるか、どの支払いを行うかを決定する。
論文 参考訳（メタデータ） (2024-09-12T07:59:10Z) - Near-Optimal Solutions of Constrained Learning Problems [85.48853063302764]
機械学習システムでは、振る舞いを縮小する必要性がますます顕在化している。
これは、双対ロバスト性変数を満たすモデルの開発に向けた最近の進歩によって証明されている。
この結果から, 豊富なパラメトリゼーションは非次元的, 有限な学習問題を効果的に緩和することが示された。
論文 参考訳（メタデータ） (2024-03-18T14:55:45Z) - Efficient Methods for Non-stationary Online Learning [67.3300478545554]
本稿では, 動的後悔と適応的後悔を最適化する効率的な手法を提案し, ラウンド当たりの投影回数を$mathcalO(log T)$から$ $1$まで削減した。
本手法は,パラメータフリーオンライン学習において開発された還元機構を基礎として,非定常オンライン手法に非自明なツイストを必要とする。
論文 参考訳（メタデータ） (2023-09-16T07:30:12Z) - Direct Heterogeneous Causal Learning for Resource Allocation Problems in
Marketing [20.9377115817821]
マーケティングは、ユーザのエンゲージメントを高め、プラットフォーム収益を改善するための重要なメカニズムである。
マーケティングにおける意思決定問題は資源配分問題として定式化され、数十年にわたって研究されてきた。
既存の作業は通常、解法を2つの完全に分離された段階、すなわち機械学習(ML)と操作研究(OR)に分割する。
論文 参考訳（メタデータ） (2022-11-28T19:27:34Z) - A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
我々は,意思決定者が長期的制約の対象となる一連の意思決定をしなければならないオンライン学習問題について検討する。
目標は、全報酬を最大化し、同時に、$T$ラウンド全体で小さな累積違反を達成することである。
本稿では,この一般クラス問題に対して,未知のモデルに基づいて報酬と制約が選択された場合と,各ラウンドで敵が選択した場合の双方において,最良世界型アルゴリズムを提示する。
論文 参考訳（メタデータ） (2022-09-15T16:59:19Z) - Online Learning with Knapsacks: the Best of Both Worlds [54.28273783164608]
オンライン学習の課題として,意思決定者が,リソース制約の有限セットに違反することなく,期待する報酬を最大化したい,という課題を提起する。
当社のフレームワークは,意思決定者がそのエビデンスを柔軟かつコスト論的に扱えるようにします。
論文 参考訳（メタデータ） (2022-02-28T12:10:48Z) - Online Allocation with Two-sided Resource Constraints [44.5635910908944]
我々は,要求が順次到着する,リソース制約の低いオンラインアロケーション問題を考える。
提案手法では, リクエスト全体を知るオフライン問題に対して, 1-O (fracepsilonalpha-epsilon)$-competitive ratioを求めるアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-12-28T02:21:06Z) - Online Optimization and Ambiguity-based Learning of Distributionally Uncertain Dynamic Systems [1.6709415233613623]
本稿では,分散的に不確実な力学系のクラスを対象とする最適化問題 (P) に対して,データ駆動型オンラインソリューションを構築するための新しい手法を提案する。
導入されたフレームワークは、パラメータ化された制御依存のあいまいさセットを通じて、分散システムの不確実性の同時学習を可能にする。
また、Nesterovの高速化段階アルゴリズムのオンライン版を導入し、その性能を分析して、分散性理論を用いてこの問題のクラスを解く。
論文 参考訳（メタデータ） (2021-02-18T01:49:06Z) - An Online Method for A Class of Distributionally Robust Optimization
with Non-Convex Objectives [54.29001037565384]
本稿では,オンライン分散ロバスト最適化(DRO)のクラスを解決するための実用的なオンライン手法を提案する。
本研究は,ネットワークの堅牢性向上のための機械学習における重要な応用を実証する。
論文 参考訳（メタデータ） (2020-06-17T20:19:25Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。