論文の概要: No-Regret Learning in Bilateral Trade via Global Budget Balance
- arxiv url: http://arxiv.org/abs/2310.12370v2
- Date: Wed, 27 Mar 2024 13:44:21 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-28 22:52:43.082294
- Title: No-Regret Learning in Bilateral Trade via Global Budget Balance
- Title（参考訳）: グローバル・バジェット・バランスによる二国間貿易におけるノンレグレット・ラーニング
- Authors: Martino Bernasconi, Matteo Castiglioni, Andrea Celli, Federico Fusco,
- Abstract要約: 我々は、様々なフィードバックモデルの下で、敵対的二元貿易のための最初のノンレグレットアルゴリズムを提供する。
フルフィードバックモデルでは、学習者は後見の最高の固定価格に対して$tilde O(sqrtT)$ regretを保証できる。
また,1ビットフィードバックを伴って,$tilde O(T3/4)$ regret upper boundを保証した学習アルゴリズムも提供する。
- 参考スコア（独自算出の注目度）: 29.514323697659613
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Bilateral trade models the problem of intermediating between two rational agents -- a seller and a buyer -- both characterized by a private valuation for an item they want to trade. We study the online learning version of the problem, in which at each time step a new seller and buyer arrive and the learner has to set prices for them without any knowledge about their (adversarially generated) valuations. In this setting, known impossibility results rule out the existence of no-regret algorithms when budget balanced has to be enforced at each time step. In this paper, we introduce the notion of \emph{global budget balance}, which only requires the learner to fulfill budget balance over the entire time horizon. Under this natural relaxation, we provide the first no-regret algorithms for adversarial bilateral trade under various feedback models. First, we show that in the full-feedback model, the learner can guarantee $\tilde O(\sqrt{T})$ regret against the best fixed prices in hindsight, and that this bound is optimal up to poly-logarithmic terms. Second, we provide a learning algorithm guaranteeing a $\tilde O(T^{3/4})$ regret upper bound with one-bit feedback, which we complement with a $\Omega(T^{5/7})$ lower bound that holds even in the two-bit feedback model. Finally, we introduce and analyze an alternative benchmark that is provably stronger than the best fixed prices in hindsight and is inspired by the literature on bandits with knapsacks.
- Abstract（参考訳）: バイラテラル取引は、売り手と買い手という2人の合理的エージェントの仲介に関する問題をモデル化している。
オンライン学習版の問題を調査し,新たな売り手と買い手が到着する度に,学習者は,その評価(逆生成)について何の知識も持たずに価格を設定する必要がある。
この設定では、既知の不合理性の結果は、予算の均衡を各ステップで実施しなければならない場合、非レグレットアルゴリズムの存在を規定する。
本稿では,時間的地平線上での予算バランスを学習者にのみ要求する「emph{global budget balance}」の概念を紹介する。
この自然緩和の下では、様々なフィードバックモデルの下で対向的二元貿易のための最初の非相対的アルゴリズムを提供する。
まず、フルフィードバックモデルにおいて、学習者は後述の最高の固定価格に対して$\tilde O(\sqrt{T})$ regretを保証でき、この境界は多対数項まで最適であることを示す。
第二に、2ビットフィードバックモデルにおいても保たれる$\Omega(T^{5/7})$ローバウンドを補完する1ビットフィードバックを持つ、$\tilde O(T^{3/4})$残念な上限を保証する学習アルゴリズムを提供する。
最後に、後見において最高の固定価格よりも確実に強い代替ベンチマークを導入・分析し、クナップサックによる盗賊に関する文献から着想を得た。
関連論文リスト
- Improved learning rates in multi-unit uniform price auctions [20.8319469276025]
複数ユニットの均一価格オークションにおけるオンライン学習の課題を,対立する入札設定に焦点をあてて検討した。
我々は,この問題の構造を活かした学習アルゴリズムが,帯域幅フィードバック下での$tildeO(K4/3T2/3)の後悔を実現することを証明した。
電力備蓄市場からインスパイアされたフィードバックモデルを導入し,すべての入札を提示する。
論文 参考訳（メタデータ） (2025-01-17T13:26:12Z) - Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback [58.66941279460248]
人からのフィードバックから学ぶことは、大言語モデル(LLM)のような生成モデルを調整する上で重要な役割を果たす
本稿では,本問題の領域内モデルについて考察する。-文脈的デュエルバンディットと敵対的フィードバックを併用し,真の嗜好ラベルを敵によって反転させることができる。
本稿では,不確実性重み付き最大推定に基づく頑健なコンテキストデュエルバンドイット(アルゴ)を提案する。
論文 参考訳（メタデータ） (2024-04-16T17:59:55Z) - An Online Learning Theory of Brokerage [3.8059763597999012]
オンライン学習の観点からトレーダー間のブローカーについて検討する。
既に研究されている他の二国間貿易問題とは異なり、指定された買い手や売り手の役割が存在しない場合に焦点を当てる。
第1の場合、最適率は$sqrtT$に低下し、第2の場合、問題は解けなくなる。
論文 参考訳（メタデータ） (2023-10-18T17:01:32Z) - Online Learning in Contextual Second-Price Pay-Per-Click Auctions [47.06746975822902]
オンライン学習は、クリック単価のオークションで学習し、そこでは、各ラウンドのT$で、学習者がいくつかのコンテキストと広告を受信する。
学習者のゴールは、彼女の後悔を最小限に抑えることであり、それは彼女の総収入と託宣戦略のギャップとして定義される。
論文 参考訳（メタデータ） (2023-10-08T07:04:22Z) - Borda Regret Minimization for Generalized Linear Dueling Bandits [65.09919504862496]
本稿では,ボルダスコアが最も高い項目を識別することを目的とした,デュエルバンディットに対するボルダ後悔最小化問題について検討する。
本稿では,多くの既存モデルをカバーする一般化線形デュエルバンドモデルのリッチクラスを提案する。
我々のアルゴリズムは$tildeO(d2/3 T2/3)$ regretを達成し、これも最適である。
論文 参考訳（メタデータ） (2023-03-15T17:59:27Z) - Repeated Bilateral Trade Against a Smoothed Adversary [5.939280057673226]
我々は、アダプティブ$sigma$-smooth敵が売り手と買い手のバリュエーションを生成する二国間取引について検討する。
本研究では、異なるフィードバックモデルの下での固定価格機構に対する後悔状態の完全な特徴付けを行う。
論文 参考訳（メタデータ） (2023-02-21T16:30:10Z) - Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics [53.62091043347035]
オンライン広告プラットフォームで競合するオートバイディングアルゴリズムのゲームについて検討する。
本稿では,全ての制約を満たすことを保証し,個人の後悔を解消する勾配に基づく学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-30T21:59:30Z) - A Reinforcement Learning Approach in Multi-Phase Second-Price Auction
Design [158.0041488194202]
多相第2価格オークションにおけるリザーブ価格の最適化について検討する。
売り手の視点からは、潜在的に非現実的な入札者の存在下で、環境を効率的に探索する必要がある。
第三に、売り手のステップごとの収益は未知であり、非線形であり、環境から直接観察することさえできない。
論文 参考訳（メタデータ） (2022-10-19T03:49:05Z) - The Best of Both Worlds: Reinforcement Learning with Logarithmic Regret
and Policy Switches [84.54669549718075]
漸進的強化学習(RL)における後悔の最小化問題について検討する。
一般関数クラスと一般モデルクラスで学ぶことに集中する。
対数的後悔境界は$O(log T)$スイッチングコストのアルゴリズムによって実現可能であることを示す。
論文 参考訳（メタデータ） (2022-03-03T02:55:55Z) - A Regret Analysis of Bilateral Trade [5.031063690574698]
我々は、売り手/買い手の相互作用のラウンド上の後悔最小化フレームワークに二国間貿易問題で初めてキャストしました。
私達の主な貢献は異なったモデルのフィードバックおよび私用評価の固定価格のメカニズムのための後悔の体制の完全な特徴付けです。
論文 参考訳（メタデータ） (2021-02-16T08:53:17Z) - Regret Minimization in Stochastic Contextual Dueling Bandits [40.17224226373741]
我々は、コンテキスト設定において、$K$武装デュエルバンディットの問題を考察する。
提案手法は, それぞれ, 後悔の保証を施した2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-02-20T06:36:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。