論文の概要: Repeated Bilateral Trade Against a Smoothed Adversary

• arxiv url: http://arxiv.org/abs/2302.10805v1
• Date: Tue, 21 Feb 2023 16:30:10 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-22 14:27:04.498054
• Title: Repeated Bilateral Trade Against a Smoothed Adversary
• Title（参考訳）: Smoothed Adversary に対する繰り返しのバイラテラル貿易
• Authors: Nicol\`o Cesa-Bianchi, Tommaso Cesari, Roberto Colomboni, Federico Fusco, Stefano Leonardi
• Abstract要約: 我々は、アダプティブ$sigma$-smooth敵が売り手と買い手のバリュエーションを生成する二国間取引について検討する。 本研究では、異なるフィードバックモデルの下での固定価格機構に対する後悔状態の完全な特徴付けを行う。
• 参考スコア（独自算出の注目度）: 5.939280057673226
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study repeated bilateral trade where an adaptive $\sigma$-smooth adversary generates the valuations of sellers and buyers. We provide a complete characterization of the regret regimes for fixed-price mechanisms under different feedback models in the two cases where the learner can post either the same or different prices to buyers and sellers. We begin by showing that the minimax regret after $T$ rounds is of order $\sqrt{T}$ in the full-feedback scenario. Under partial feedback, any algorithm that has to post the same price to buyers and sellers suffers worst-case linear regret. However, when the learner can post two different prices at each round, we design an algorithm enjoying regret of order $T^{3/4}$ ignoring log factors. We prove that this rate is optimal by presenting a surprising $T^{3/4}$ lower bound, which is the main technical contribution of the paper.
• Abstract（参考訳）: 我々は、アダプティブ$\sigma$-smooth敵が売り手と買い手のバリュエーションを生成する二国間貿易を繰り返す。 学習者が購入者や販売者に対して同じまたは異なる価格を投稿できる2つのケースにおいて、異なるフィードバックモデルの下で固定価格メカニズムに対する後悔の制度を完全に特徴づける。 まず、$T$ラウンド後のミニマックス後悔は、フルフィードバックシナリオにおいて$\sqrt{T}$であることを示す。 部分的なフィードバックの下では、買い手や売り手に同じ価格を投稿しなければならないアルゴリズムは、最悪の線形後悔に悩まされる。 しかし、学習者が各ラウンドで2つの異なる価格を提示できる場合、ログファクタを無視する$T^{3/4}を後悔するアルゴリズムを設計する。 この速度は驚くべき$t^{3/4}$下限を示して最適であることを証明し、これが論文の主な技術的貢献である。

関連論文リスト

• Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback [58.66941279460248]
  人からのフィードバックから学ぶことは、大言語モデル(LLM)のような生成モデルを調整する上で重要な役割を果たす 本稿では,本問題の領域内モデルについて考察する。-文脈的デュエルバンディットと敵対的フィードバックを併用し,真の嗜好ラベルを敵によって反転させることができる。 本稿では,不確実性重み付き最大推定に基づく頑健なコンテキストデュエルバンドイット(アルゴ)を提案する。
  論文  参考訳（メタデータ） (2024-04-16T17:59:55Z)
• No-Regret Learning in Bilateral Trade via Global Budget Balance [29.514323697659613]
  我々は、様々なフィードバックモデルの下で、敵対的二元貿易のための最初のノンレグレットアルゴリズムを提供する。 フルフィードバックモデルでは、学習者は後見の最高の固定価格に対して$tilde O(sqrtT)$ regretを保証できる。 また,1ビットフィードバックを伴って,$tilde O(T3/4)$ regret upper boundを保証した学習アルゴリズムも提供する。
  論文  参考訳（メタデータ） (2023-10-18T22:34:32Z)
• 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)
• 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)
• Double Auctions with Two-sided Bandit Feedback [11.334374665364214]
  ダブルオークションは、複数の買い手と売り手の間の商品の分散移動を可能にする。 信頼関係に基づく入札を行い、参加者の間には「平均価格」が効率的な価格発見をもたらすことを示す。 本論文は,両面の市場において,両面から学習が必要な不確実な嗜好を持つ分散学習アルゴリズムを初めて提供するものである。
  論文  参考訳（メタデータ） (2022-08-13T01:03:34Z)
• The price of unfairness in linear bandits with biased feedback [62.25313751895011]
  線形帯域フィードバックによる逐次意思決定の問題点について検討する。 その結果,不偏フィードバック下で得られたdT 1/2 log(T) の後悔率よりも最悪の後悔率が高いことがわかった。 興味深いことに、ギャップ依存率によって、問題はバイアスのないものほど難しくない非自明なインスタンスの存在が明らかになる。
  論文  参考訳（メタデータ） (2022-03-18T08:03:20Z)
• The Best of Both Worlds: Reinforcement Learning with Logarithmic Regret and Policy Switches [84.54669549718075]
  漸進的強化学習(RL)における後悔の最小化問題について検討する。 一般関数クラスと一般モデルクラスで学ぶことに集中する。 対数的後悔境界は$O(log T)$スイッチングコストのアルゴリズムによって実現可能であることを示す。
  論文  参考訳（メタデータ） (2022-03-03T02:55:55Z)
• Bilateral Trade: A Regret Minimization Perspective [5.031063690574698]
  我々は、この二国間貿易問題を、売り手/買い手の相互作用のラウンドでT$以上の最小化フレームワークに配置した。 我々の主な貢献は、異なるフィードバックモデルとプライベートバリュエーションを持つ固定価格機構に対する後悔の体制の完全な評価である。
  論文  参考訳（メタデータ） (2021-09-08T22:11:48Z)

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

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