論文の概要: Regret Minimization in Bilateral Trade With Perturbed Markets
- arxiv url: http://arxiv.org/abs/2605.10475v1
- Date: Mon, 11 May 2026 12:37:53 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-05-12 23:28:50.814029
- Title: Regret Minimization in Bilateral Trade With Perturbed Markets
- Title（参考訳）: 市場混乱に伴う二国間貿易のレグレット最小化
- Authors: Anna Lunghi, Matteo Castiglioni, Alberto Marchesi,
- Abstract要約: 我々は、世界財政収支の制約を受ける買い手・売り手取引所における取引所(GFT)からの利得の最大化の問題に対処する。
対向的な環境は、最高の固定価格メカニズムに対する非回帰学習を可能にする。
提案アルゴリズムは, 予算バランスの悪いベースラインに対して, 最悪値である$tildemathcalO(T3/4)$ regret を維持できる。
- 参考スコア（独自算出の注目度）: 25.375074054942434
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We address the problem of maximizing Gain from Trade (GFT) in repeated buyer-seller exchanges subject to global budget balance constraints. While this problem is well-understood in purely adversarial and stochastic settings, these environments exhibit a sharp dichotomy: adversarial environments allow for no-regret learning against the best fixed-price mechanism, whereas stochastic environments allow for no-regret learning against the best distribution over prices that is budget balanced in expectation. This gap is significant, as policies balanced in expectation can increase the GFT by a multiplicative factor of two. In this work, we bridge these extremes by studying perturbed markets, where an underlying stochastic distribution is subject to an adversarial corruption $C$. We design an algorithm that adaptively scales with the level of corruption, achieving an $\tilde{\mathcal{O}}(T^{3/4}) + \mathcal{O}(C\log(T))$ regret bound against the best budget-balanced distribution over prices. Simultaneously, our algorithm maintains the worst-case $\tilde{\mathcal{O}}(T^{3/4})$ regret bound relative to a per-round budget-balanced baseline, ensuring optimality even in fully adversarial environments.
- Abstract（参考訳）: 我々は、世界財政収支の制約を受ける買い手・売り手取引所における取引所(GFT)からの利得の最大化の問題に対処する。
敵対的環境は、最高の固定価格のメカニズムに対して、非相対的学習を可能にするが、確率的環境は、予想される予算のバランスを保った価格に対する最良の分布に対して、非相対的学習を可能にする。
このギャップは、期待のバランスの取れたポリシーが2倍の乗算係数でGFTを増加させる可能性があるため、重要である。
この研究では、これらの極端を摂動市場の研究によって橋渡しし、基礎となる確率分布は敵の汚職によって$C$となる。
我々は, 汚職の程度で適応的にスケールするアルゴリズムを設計し, 価格に対する最良の予算均衡分布に対して$\tilde{\mathcal{O}}(T^{3/4}) + \mathcal{O}(C\log(T))$ 後悔の意を表す。
同時に、我々のアルゴリズムは、全予算バランスのベースラインに対して最悪の場合$\tilde{\mathcal{O}}(T^{3/4})$ regret bound を維持し、完全な対向環境においても最適性を確保する。
関連論文リスト
- Reinforcement Learning from Multi-Source Imperfect Preferences: Best-of-Both-Regimes Regret [71.69884486156359]
我々は, 累積的不完全化予算を用いて, エンフルティソースの不完全性選好からエピソードRLを考察した。
我々は,最良な登録行動を示す,後悔$tildeO(sqrtK/M+)$の統一アルゴリズムを提案する。
論文 参考訳（メタデータ） (2026-03-20T19:34:53Z) - Stability and Generalization of Push-Sum Based Decentralized Optimization over Directed Graphs [55.77845440440496]
プッシュベースの分散通信は、情報交換が非対称である可能性のある通信ネットワークの最適化を可能にする。
我々は、グラディエント・プッシュ(SGP)アルゴリズムのための統一的な一様安定性フレームワークを開発する。
重要な技術的要素は、2つの量に束縛された不均衡認識の一般化である。
論文 参考訳（メタデータ） (2026-02-24T05:32:03Z) - Nearly Tight Regret Bounds for Profit Maximization in Bilateral Trade [14.182863671689836]
バイラテラル取引は、売り手と買い手という2つの戦略エージェントの仲介を行うタスクをモデル化する。
我々は,この問題をブローカーの観点から,後悔の最小化フレームワークを用いて検討する。
本稿では,売り手と評価を引いた場合,約$tildeO(sqrtT)=後悔を保証できる学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-09-26T16:42:05Z) - Follow-the-Perturbed-Leader Approaches Best-of-Both-Worlds for the m-Set Semi-Bandit Problems [18.74680577173648]
我々は、学習者が$m$の腕から$m$の腕を正確に選択する、$m$セット半帯域問題の一般的な場合を考える。
また, Fr'echet 摂動を持つFTPL は, 対向的な設定で, $mathcalO(sqrtnm(sqrtdlog(d)+m5/6)$ をほぼ最適に再現できることを示す。
論文 参考訳（メタデータ） (2025-04-09T22:07:01Z) - Contextual Combinatorial Bandits with Probabilistically Triggered Arms [55.9237004478033]
確率的に誘発される腕(C$2$MAB-T)を様々な滑らかさ条件下で検討した。
トリガー変調 (TPM) 条件の下では、C$2$-UC-Tアルゴリズムを考案し、後悔すべき$tildeO(dsqrtT)$を導出する。
論文 参考訳（メタデータ） (2023-03-30T02:51:00Z) - Autoregressive Bandits [58.46584210388307]
本稿では,オンライン学習環境であるAutoregressive Banditsを提案する。
報酬プロセスの軽微な仮定の下では、最適ポリシーを便利に計算できることが示される。
次に、新しい楽観的後悔最小化アルゴリズム、すなわちAutoRegressive Upper Confidence Bound (AR-UCB)を考案し、$widetildemathcalO left( frac(k+1)3/2sqrtnT (1-G)のサブ線形後悔を被る。
論文 参考訳（メタデータ） (2022-12-12T21:37:36Z) - Adversarially Robust Multi-Armed Bandit Algorithm with
Variance-Dependent Regret Bounds [34.37963000493442]
本稿では,マルチアーム・バンディット(MAB)問題について考察し,両対向的条件下でほぼ最適に機能する,新たなベスト・オブ・ボス・ワールド(BOBW)アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-06-14T12:58:46Z) - Near-Optimal No-Regret Learning for Correlated Equilibria in
Multi-Player General-Sum Games [104.74734408204749]
マルチプレイヤーの汎用正規形式ゲームにおいて,OMWU(Optimistic Multiplicative Weights Update)を用いているエージェントが全員,O(textrmpolylog(T))$(T$)$(T$)$(OMWU)$(OMWU)$(OMWU)$(OMWU)$(OMWU)$)であることを示す。
外部の後悔から内部の後悔へと結果を拡張し、後悔を交換することで、近似した平衡に収束する非結合学習ダイナミクスを確立する。
論文 参考訳（メタデータ） (2021-11-11T01:19:53Z) - On Optimal Robustness to Adversarial Corruption in Online Decision
Problems [27.68461396741871]
最適ロバスト性は汚損量に対する平方根依存性によって表現できることを示す。
多武装バンディット問題に対しては、対数係数までほぼ狭い下界も提供する。
論文 参考訳（メタデータ） (2021-09-22T18:26:45Z) - The Interplay between Distribution Parameters and the
Accuracy-Robustness Tradeoff in Classification [0.0]
アドリラルトレーニングは、通常のモデルに比べて自然(未成熟)の例では正確でないモデルをもたらす傾向にある。
これは、アルゴリズムの欠点か、トレーニングデータ分散の基本的な性質によるものとみなすことができる。
本研究では,二進ガウス混合分類問題の下で後者のケースに焦点をあてる。
論文 参考訳（メタデータ） (2021-07-01T06:57:50Z) - Non-Convex SGD Learns Halfspaces with Adversarial Label Noise [50.659479930171585]
分布固有モデルにおいて,同種半空間の学習を代理する問題に対する解を示す。
任意の凸分布において、誤分類誤差は本質的にハーフスペースの誤分類誤差につながることを示す。
論文 参考訳（メタデータ） (2020-06-11T18:55:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。