論文の概要: Learning in Budgeted Auctions with Spacing Objectives

• arxiv url: http://arxiv.org/abs/2411.04843v1
• Date: Thu, 07 Nov 2024 16:31:31 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-08 19:37:11.922435
• Title: Learning in Budgeted Auctions with Spacing Objectives
• Title（参考訳）: スペーシング・オブジェクトを用いた予算入札における学習
• Authors: Giannis Fikioris, Robert Kleinberg, Yoav Kolumbus, Raunak Kumar, Yishay Mansour, Éva Tardos,
• Abstract要約: 多くのオークションでは、参加者は勝利の頻度だけでなく、勝利が時間とともにどのように分配されるかに気を配る。 我々は,この現象の簡単なモデルを導入し,勝利の値が最後の勝利以来のコンケーブ関数であるような,予算付きオークションとしてモデル化する。 状態に依存しない戦略は変換の不確かさを伴わずに線形後悔を引き起こすことを示す。
• 参考スコア（独自算出の注目度）: 41.63843740537835
• License:
• Abstract: In many repeated auction settings, participants care not only about how frequently they win but also how their winnings are distributed over time. This problem arises in various practical domains where avoiding congested demand is crucial, such as online retail sales and compute services, as well as in advertising campaigns that require sustained visibility over time. We introduce a simple model of this phenomenon, modeling it as a budgeted auction where the value of a win is a concave function of the time since the last win. This implies that for a given number of wins, even spacing over time is optimal. We also extend our model and results to the case when not all wins result in "conversions" (realization of actual gains), and the probability of conversion depends on a context. The goal is to maximize and evenly space conversions rather than just wins. We study the optimal policies for this setting in second-price auctions and offer learning algorithms for the bidders that achieve low regret against the optimal bidding policy in a Bayesian online setting. Our main result is a computationally efficient online learning algorithm that achieves $\tilde O(\sqrt T)$ regret. We achieve this by showing that an infinite-horizon Markov decision process (MDP) with the budget constraint in expectation is essentially equivalent to our problem, even when limiting that MDP to a very small number of states. The algorithm achieves low regret by learning a bidding policy that chooses bids as a function of the context and the system's state, which will be the time elapsed since the last win (or conversion). We show that state-independent strategies incur linear regret even without uncertainty of conversions. We complement this by showing that there are state-independent strategies that, while still having linear regret, achieve a $(1-\frac 1 e)$ approximation to the optimal reward.
• Abstract（参考訳）: 多くのオークション設定では、参加者は勝利の頻度だけでなく、勝利が時間とともにどのように分配されるかにも気を配る。 この問題は、オンライン小売販売や計算サービスなど、密集した需要を避けることが不可欠である様々な実践領域や、持続的な可視性を必要とする広告キャンペーンで発生する。 我々は,この現象の簡単なモデルを導入し,勝利の値が最後の勝利以来のコンケーブ関数であるような,予算付きオークションとしてモデル化する。 これは、与えられた勝利数に対して、時間が経過しても最適であることを意味する。 また、全ての勝利が「変換」(実際のゲインの実現)をもたらすわけではない場合に、我々のモデルと結果も拡張し、変換の確率は文脈に依存する。 ゴールは、勝利だけでなく、空間変換の最大化と均等化だ。 本研究では,このセッティングの最適政策を第2価格オークションで検討し,ベイズオンラインセッティングにおける最適入札ポリシーに対する後悔度を低く抑えるような入札者のための学習アルゴリズムを提案する。 我々の主な成果は、計算効率のよいオンライン学習アルゴリズムであり、そのアルゴリズムは、$\tilde O(\sqrt T)$ regretを達成する。 我々は,MDP を少数の州に制限しても,予算制約のある無限水平マルコフ決定過程 (MDP) が本質的に我々の問題と等価であることを示す。 このアルゴリズムは、入札をコンテキストとシステムの状態の関数として選択する入札ポリシーを学習することで、低い後悔を達成する。 状態に依存しない戦略は変換の不確かさを伴わずに線形後悔を引き起こすことを示す。 線形後悔はあるものの、最適報酬への近似として(1-\frac 1 e)$(1-\frac 1 e)を達成できる状態に依存しない戦略が存在することを示すことでこれを補完する。

関連論文リスト

• Selling Joint Ads: A Regret Minimization Perspective [7.288063443108292]
  オンライン小売によるモチベーションにより、一品(広告スロットなど)を2つの非排除購入者(商店、ブランド等)に販売する問題を考える。 この問題は、例えば、マーチャントとブランドが商品を宣伝するために競売に協力して入札する状況と、表示されている広告の恩恵を捉えている。 メカニズムは2つの入札を収集し、どちらを割り当てるか、どの支払いを行うかを決定する。
  論文  参考訳（メタデータ） (2024-09-12T07:59:10Z)
• Online Reinforcement Learning in Markov Decision Process Using Linear Programming [1.0878040851638]
  マルコフ決定過程(MDP)におけるオンライン強化学習について検討した。 我々は,高い確率で$widetildeO(LXsqrtTA)$ regretを実現する,シンプルで効率的なモデルベースアルゴリズムを考案した。
  論文  参考訳（メタデータ） (2023-03-31T22:21:41Z)
• Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics [53.62091043347035]
  オンライン広告プラットフォームで競合するオートバイディングアルゴリズムのゲームについて検討する。 本稿では,全ての制約を満たすことを保証し,個人の後悔を解消する勾配に基づく学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-30T21:59:30Z)
• 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)
• A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
  我々は,意思決定者が長期的制約の対象となる一連の意思決定をしなければならないオンライン学習問題について検討する。 目標は、全報酬を最大化し、同時に、$T$ラウンド全体で小さな累積違反を達成することである。 本稿では,この一般クラス問題に対して,未知のモデルに基づいて報酬と制約が選択された場合と,各ラウンドで敵が選択した場合の双方において,最良世界型アルゴリズムを提示する。
  論文  参考訳（メタデータ） (2022-09-15T16:59:19Z)
• The Best of Both Worlds: Reinforcement Learning with Logarithmic Regret and Policy Switches [84.54669549718075]
  漸進的強化学習(RL)における後悔の最小化問題について検討する。 一般関数クラスと一般モデルクラスで学ぶことに集中する。 対数的後悔境界は$O(log T)$スイッチングコストのアルゴリズムによって実現可能であることを示す。
  論文  参考訳（メタデータ） (2022-03-03T02:55:55Z)
• Fast Rate Learning in Stochastic First Price Bidding [0.0]
  ファーストプライスのオークションは、プログラム広告におけるビックレーのオークションに基づく伝統的な入札アプローチを大きく置き換えている。 対戦相手の最大入札分布が分かっている場合, 後悔度を著しく低くする方法を示す。 我々のアルゴリズムは、様々な入札分布の文献で提案されている選択肢よりもはるかに高速に収束する。
  論文  参考訳（メタデータ） (2021-07-05T07:48:52Z)
• Online Markov Decision Processes with Aggregate Bandit Feedback [74.85532145498742]
  本稿では,オンライン有限水平マルコフ決定過程の新たな変種について検討する。 各エピソードにおいて、学習者は、エピソードの選択した方針によって実現された軌道に沿って蓄積された損失を被り、総括的盗聴フィードバックを観察する。 我々の主な結果は計算効率のよいアルゴリズムで、$O(sqrtK)$ regret for this set, where $K$ is the number of episodes。
  論文  参考訳（メタデータ） (2021-01-31T16:49:07Z)
• Efficient Algorithms for Stochastic Repeated Second-price Auctions [0.0]
  我々は,繰り返し競売を行うための効率的な逐次入札戦略を開発する。 この問題に対する最初のパラメトリック下界を提供する。 本稿では,探索時コミット帯域幅アルゴリズムを思い起こさせる,より説明可能な戦略を提案する。
  論文  参考訳（メタデータ） (2020-11-10T12:45:02Z)
• Scalable Bid Landscape Forecasting in Real-time Bidding [12.692521867728091]
  プログラム広告では、広告スロットは通常、第二価格(SP)オークションを使ってリアルタイムで販売される。 SPでは、1つの項目に対して、各入札者の支配的な戦略は、入札者の視点から真の価値を入札することである。 本稿では,ヘテロセダスティックな完全パラメトリック・レグレッション・アプローチと混合密度・レグレッション・ネットワークを提案する。
  論文  参考訳（メタデータ） (2020-01-18T03:20:05Z)

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

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