論文の概要: Online Learning in Contextual Second-Price Pay-Per-Click Auctions
- arxiv url: http://arxiv.org/abs/2310.05047v1
- Date: Sun, 8 Oct 2023 07:04:22 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-12 13:05:46.722645
- Title: Online Learning in Contextual Second-Price Pay-Per-Click Auctions
- Title（参考訳）: クリック単価オークションにおけるオンライン学習
- Authors: Mengxiao Zhang, Haipeng Luo
- Abstract要約: オンライン学習は、クリック単価のオークションで学習し、そこでは、各ラウンドのT$で、学習者がいくつかのコンテキストと広告を受信する。
学習者のゴールは、彼女の後悔を最小限に抑えることであり、それは彼女の総収入と託宣戦略のギャップとして定義される。
- 参考スコア（独自算出の注目度）: 47.06746975822902
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study online learning in contextual pay-per-click auctions where at each
of the $T$ rounds, the learner receives some context along with a set of ads
and needs to make an estimate on their click-through rate (CTR) in order to run
a second-price pay-per-click auction. The learner's goal is to minimize her
regret, defined as the gap between her total revenue and that of an oracle
strategy that always makes perfect CTR predictions. We first show that
$\sqrt{T}$-regret is obtainable via a computationally inefficient algorithm and
that it is unavoidable since our algorithm is no easier than the classical
multi-armed bandit problem. A by-product of our results is a $\sqrt{T}$-regret
bound for the simpler non-contextual setting, improving upon a recent work of
[Feng et al., 2023] by removing the inverse CTR dependency that could be
arbitrarily large. Then, borrowing ideas from recent advances on efficient
contextual bandit algorithms, we develop two practically efficient contextual
auction algorithms: the first one uses the exponential weight scheme with
optimistic square errors and maintains the same $\sqrt{T}$-regret bound, while
the second one reduces the problem to online regression via a simple
epsilon-greedy strategy, albeit with a worse regret bound. Finally, we conduct
experiments on a synthetic dataset to showcase the effectiveness and superior
performance of our algorithms.
- Abstract（参考訳）: そこで我々は,$t$ ラウンドのそれぞれにおいて,学習者がいくつかのコンテキストを広告と共に受け取り,クリックスルー率 (ctr) を推定し,第2価格のペイ・パー・クリックオークションを実行する必要がある,という状況下でのオンライン学習について検討した。
学習者の目標は、彼女の全収入と、常に完璧なCTR予測を行う神託戦略のギャップとして定義される後悔を最小限にすることである。
まず,$\sqrt{t}$-regret が計算効率の悪いアルゴリズムによって得られること,また,従来のマルチアーム付きバンディット問題よりもアルゴリズムが容易ではないこと,が示される。
我々の結果の副産物は、より単純な非文脈設定に対して$\sqrt{T}$-regret 境界であり、任意に大きい逆 CTR 依存を取り除くことで [Feng et al., 2023] の最近の研究を改善している。
そして、近年の効率的な文脈的バンディットアルゴリズムの進歩からアイデアを借りて、2つの実用的な文脈的オークションアルゴリズムを開発する: 1つは楽観的な2乗誤差を持つ指数的重み付けスキームを使い、同じ$\sqrt{T}$-regret境界を維持し、もう1つは単純なエプシロン・グレーディ戦略によって問題をオンライン回帰に還元する。
最後に,合成データセットを用いた実験を行い,アルゴリズムの有効性と優れた性能を示す。
関連論文リスト
- Strategically-Robust Learning Algorithms for Bidding in First-Price Auctions [11.988955088595858]
ゲーム理論と機械学習のインターフェースにおいて,プライスオークションを繰り返し競うことの学習は基本的な問題である。
本稿では,プライスオークションにおける純ストラテジー入札のための新しいコンケーブの定式化を提案し,この問題に対する自然なグラディエント・アセンセント・アルゴリズムの解析に利用した。
論文 参考訳（メタデータ） (2024-02-12T01:33:33Z) - Contextual Bandits and Imitation Learning via Preference-Based Active
Queries [17.73844193143454]
本研究では,学習者が実行された行動報酬の直接的な知識を欠いている文脈的包帯と模倣学習の問題を考察する。
その代わり、学習者は各ラウンドのエキスパートに積極的に問い合わせて2つのアクションを比較し、ノイズの多い好みのフィードバックを受け取ることができる。
学習者の目的は、実行されたアクションに関連する後悔を最小限に抑えると同時に、専門家が行った比較クエリの数を最小化することである。
論文 参考訳（メタデータ） (2023-07-24T16:36:04Z) - The Best of Both Worlds: Reinforcement Learning with Logarithmic Regret
and Policy Switches [84.54669549718075]
漸進的強化学習(RL)における後悔の最小化問題について検討する。
一般関数クラスと一般モデルクラスで学ぶことに集中する。
対数的後悔境界は$O(log T)$スイッチングコストのアルゴリズムによって実現可能であることを示す。
論文 参考訳（メタデータ） (2022-03-03T02:55:55Z) - Efficient and Optimal Algorithms for Contextual Dueling Bandits under
Realizability [59.81339109121384]
我々は,学習者が文脈情報を用いて2つの決定を下す連続的な決定設定であるK$コンテキストデュエルバンディット問題について検討するが,一方の判断が他方よりも優れていることを示唆する強調基準に基づくフィードバックのみを観察する。
提案手法は, 最善応答後悔という新たな概念に対して, 最善応答後悔に対する最適後悔率を実現するアルゴリズムである。
論文 参考訳（メタデータ） (2021-11-24T07:14:57Z) - Linear Contextual Bandits with Adversarial Corruptions [91.38793800392108]
本稿では,敵対的腐敗の存在下での線形文脈的包帯問題について検討する。
逆汚染レベルに適応する分散認識アルゴリズムをC$で提案する。
論文 参考訳（メタデータ） (2021-10-25T02:53:24Z) - 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) - Impact of Representation Learning in Linear Bandits [83.17684841392754]
本研究では,表現学習が帯域幅問題の効率性を向上させる方法について検討する。
我々は,$widetildeO(TsqrtkN + sqrtdkNT)$ regretを達成する新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-10-13T16:35:30Z) - Regret Minimization in Stochastic Contextual Dueling Bandits [40.17224226373741]
我々は、コンテキスト設定において、$K$武装デュエルバンディットの問題を考察する。
提案手法は, それぞれ, 後悔の保証を施した2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-02-20T06:36:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。