論文の概要: Contextual Online Bilateral Trade

• arxiv url: http://arxiv.org/abs/2602.12903v1
• Date: Fri, 13 Feb 2026 13:03:10 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-16 23:37:53.95504
• Title: Contextual Online Bilateral Trade
• Title（参考訳）: コンテキストオンラインバイラテラル取引
• Authors: Romain Cosson, Federico Fusco, Anupam Gupta, Stefano Leonardi, Renato Paes Leme, Matteo Russo,
• Abstract要約: 我々は、貿易と利益の2つの目的について研究する。 我々は、取引の利益のために$O(dlog d)$後悔するアルゴリズムを設計し、利益のために$O(dlog T + dlog d)$後悔するアルゴリズムを設計する。
• 参考スコア（独自算出の注目度）: 18.8734045754182
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study repeated bilateral trade when the valuations of the sellers and the buyers are contextual. More precisely, the agents' valuations are given by the inner product of a context vector with two unknown $d$-dimensional vectors -- one for the buyers and one for the sellers. At each time step $t$, the learner receives a context and posts two prices, one for the seller and one for the buyer, and the trade happens if both agents accept their price. We study two objectives for this problem, gain from trade and profit, proving no-regret with respect to a surprisingly strong benchmark: the best omniscient dynamic strategy. In the natural scenario where the learner observes \emph{separately} whether the agents accept their price -- the so-called \emph{two-bit} feedback -- we design algorithms that achieve $O(d\log d)$ regret for gain from trade, and $O(d \log\log T + d\log d)$ regret for profit maximization. Both results are tight, up to the $\log(d)$ factor, and implement per-step budget balance, meaning that the learner never incurs negative profit. In the less informative \emph{one-bit} feedback model, the learner only observes whether a trade happens or not. For this scenario, we show that the tight two-bit regret regimes are still attainable, at the cost of allowing the learner to possibly incur a small negative profit of order $O(d\log d)$, which is notably independent of the time horizon. As a final set of results, we investigate the combination of one-bit feedback and per-step budget balance. There, we design an algorithm for gain from trade that suffers regret independent of the time horizon, but \emph{exponential} in the dimension $d$. For profit maximization, we maintain this exponential dependence on the dimension, which gets multiplied by a $\log T$ factor.
• Abstract（参考訳）: 我々は、売り手と買い手の評価額が文脈的である場合に、二国間貿易を繰り返す。 より正確には、エージェントのバリュエーションは、2つの未知の$d$次元ベクトルを持つコンテキストベクトルの内部積によって与えられる。 各ステップ$t$で、学習者はコンテキストを受け取り、売り手と買い手のための2つの価格を投稿し、双方のエージェントが価格を受け入れると取引が行われる。 この問題に対する2つの目標、貿易と利益の獲得、驚くほど強いベンチマークに対する不利益の証明、そして最高の全能的ダイナミック戦略について研究する。 学習者が、エージェントが価格を受け入れるかどうかを観察する自然なシナリオ -- いわゆる "emph{two-bit}" フィードバック -- では、貿易による利益を後悔する$O(d\log d)と利益を最大化する$O(d \log\log T + d\log d)を後悔する$O(d \log\log T + d\log d)を達成できるアルゴリズムを設計する。 どちらの結果も、$\log(d)$ factorまで厳格であり、ステップごとの予算バランスを実装している。 情報に乏しい 'emph{one-bit} フィードバックモデルでは、学習者は取引が発生するかどうかのみを観察する。 このシナリオでは、厳密な2ビットの後悔体制が依然として達成可能であることを示し、学習者が、時間的地平線から特に独立な$O(d\log d)$の小さな負の利益を得られることを許容するコストで示している。 最終結果として,1ビットフィードバックとステップ単位の予算残高の組み合わせについて検討する。 ここでは、時間軸によらず後悔する貿易から得られるアルゴリズムを設計するが、次元$d$で \emph{exponential} を設計する。 利益の最大化のために、この指数関数的な次元依存を保ち、これは$\log T$ 因子によって乗算される。

関連論文リスト

• Nonparametric Contextual Online Bilateral Trade [15.586783656868706]
  文脈的オンライン二国間貿易の問題について検討する。 学習者の目標は、両者間の貿易を促進するために価格を公表することである。 階層木構築による文脈情報を活用するアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2026-02-13T13:03:30Z)
• Reinforcement Learning with Segment Feedback [56.54271464134885]
  状態ごとの反応フィードバックと軌道フィードバックのギャップを埋める一般的なパラダイムを提供するRLというモデルを考える。 バイナリフィードバックの下では、$m$のセグメント数の増加は指数率で後悔を減少させるが、驚くべきことに、和フィードバックの下では、$m$の増加は後悔を著しく減少させるものではない。
  論文  参考訳（メタデータ） (2025-02-03T23:08:42Z)
• Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback [58.66941279460248]
  人からのフィードバックから学ぶことは、大言語モデル(LLM)のような生成モデルを調整する上で重要な役割を果たす 本稿では,このドメイン内のモデルについて考察する。-文脈的デュエルバンディット(contextual dueling bandits)と,正の選好ラベルを相手によって反転させることができる対向フィードバック(reversarial feedback)について考察する。 本稿では,不確実性重み付き最大推定に基づく頑健なコンテキストデュエルバンドイット(RCDB)を提案する。
  論文  参考訳（メタデータ） (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)
• Repeated Bilateral Trade Against a Smoothed Adversary [5.939280057673226]
  我々は、アダプティブ$sigma$-smooth敵が売り手と買い手のバリュエーションを生成する二国間取引について検討する。 本研究では、異なるフィードバックモデルの下での固定価格機構に対する後悔状態の完全な特徴付けを行う。
  論文  参考訳（メタデータ） (2023-02-21T16:30:10Z)
• Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes [62.90204655228324]
  我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。 我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
  論文  参考訳（メタデータ） (2022-10-20T21:32:01Z)
• Minimax-Optimal Multi-Agent RL in Zero-Sum Markov Games With a Generative Model [50.38446482252857]
  2人プレイのゼロサムマルコフゲームは多エージェント強化学習においておそらく最も基本的な設定である。 我々は,$$ widetildeObiggを用いて,$varepsilon$-approximate Markov NEポリシーを学習する学習アルゴリズムを開発した。 我々は、分散型量の役割を明確にするFTRLに対する洗練された後悔境界を導出する。
  論文  参考訳（メタデータ） (2022-08-22T17:24:55Z)
• The Best of Both Worlds: Reinforcement Learning with Logarithmic Regret and Policy Switches [84.54669549718075]
  漸進的強化学習(RL)における後悔の最小化問題について検討する。 一般関数クラスと一般モデルクラスで学ぶことに集中する。 対数的後悔境界は$O(log T)$スイッチングコストのアルゴリズムによって実現可能であることを示す。
  論文  参考訳（メタデータ） (2022-03-03T02:55:55Z)

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

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