論文の概要: No-Regret Learning in Bilateral Trade via Global Budget Balance
- arxiv url: http://arxiv.org/abs/2310.12370v1
- Date: Wed, 18 Oct 2023 22:34:32 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-20 17:36:20.827215
- Title: No-Regret Learning in Bilateral Trade via Global Budget Balance
- Title（参考訳）: グローバル予算均衡による二国間貿易におけるノンレグレット学習
- Authors: Martino Bernasconi, Matteo Castiglioni, Andrea Celli, Federico Fusco
- Abstract要約: 問題のオンライン版を調査し、各段階で新しい売り手と買い手が到着する。
学習者の仕事は、各エージェントの価格を設定することであり、その評価について何の知識も持たない。
グローバルな予算バランスを必要とすることにより、二国間貿易のための最初の非レグレットアルゴリズムを提供する。
- 参考スコア（独自算出の注目度）: 32.24227834513534
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Bilateral trade revolves around the challenge of facilitating transactions
between two strategic agents -- a seller and a buyer -- both of whom have a
private valuations for the item. We study the online version of the problem, in
which at each time step a new seller and buyer arrive. The learner's task is to
set a price for each agent, without any knowledge about their valuations. The
sequence of sellers and buyers is chosen by an oblivious adversary. In this
setting, known negative results rule out the possibility of designing
algorithms with sublinear regret when the learner has to guarantee budget
balance for each iteration. In this paper, we introduce the notion of global
budget balance, which requires the agent to be budget balance only over the
entire time horizon. By requiring global budget balance, we provide the first
no-regret algorithms for bilateral trade with adversarial inputs 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, which is order-wise optimal. Then, in the case of partial feedback
models, we provide an algorithm guaranteeing a $\tilde{O}(T^{3/4})$ regret
upper bound with one-bit feedback, which we complement with a nearly-matching
lower bound. Finally, we investigate how these results vary when measuring
regret using an alternative benchmark.
- Abstract（参考訳）: 二国間貿易は、2つの戦略エージェント(売り手と買い手)の取引を促進するという課題を中心に展開している。
我々は、問題のオンラインバージョンを調査し、各段階で新しい売り手と買い手が到着する。
学習者の仕事は、各エージェントの価格を設定することであり、その評価について何の知識も持たない。
売り手と買い手の連続は、不可解な敵によって選択される。
この設定では、既知の負の結果は、学習者が反復ごとに予算バランスを保証しなければならない場合に、サブ線形後悔を伴うアルゴリズムを設計する可能性を排除している。
本稿では,グローバルな予算バランスの概念を紹介する。これは,時間的地平線全体を通してのみ,エージェントが予算バランスを取ることを必要とする。
グローバル予算均衡を求めることにより,様々なフィードバックモデルにおいて,対向入力との双方向取引のための最初のno-regretアルゴリズムを提供する。
まず、フルフィードバックモデルにおいて学習者は、従順に最適である最高の固定価格に対して$\tilde{o}(\sqrt{t})$ regretを保証できることを示す。
そして、部分フィードバックモデルの場合、1ビットフィードバックで$\tilde{O}(T^{3/4})$残念な上限を保証し、ほぼ一致する下限を補完するアルゴリズムを提供する。
最後に,代替ベンチマークを用いて後悔度を測定する際に,これらの結果がどのように変化するかを検討する。
関連論文リスト
- 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) - An $α$-regret analysis of Adversarial Bilateral Trade [10.275531964940425]
我々は、売り手と買い手のバリュエーションが完全に任意であるシーケンシャルな二国間取引を調査する。
我々は、社会福祉よりも近づきにくい貿易からの利益を考えます。
論文 参考訳（メタデータ） (2022-10-13T08:57:30Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。