Fugu-MT 論文翻訳(概要): Better Regret Rates in Bilateral Trade via Sublinear Budget Violation

論文の概要: Better Regret Rates in Bilateral Trade via Sublinear Budget Violation

arxiv url: http://arxiv.org/abs/2507.11419v1
Date: Tue, 15 Jul 2025 15:45:36 GMT
ステータス: 翻訳完了
システム内更新日: 2025-07-16 19:46:03.175504
Title: Better Regret Rates in Bilateral Trade via Sublinear Budget Violation
Title（参考訳）: 減税による二国間貿易のレグレットレート改善
Authors: Anna Lunghi, Matteo Castiglioni, Alberto Marchesi,
Abstract要約: 我々は,世界予算収支の制約に違反した場合に,最適な後悔率がどのように変化するかを検討する。この結果を、一致した低い境界で補うことで、後悔と予算違反のトレードオフを完全に特徴づけます。
参考スコア（独自算出の注目度）: 28.647867626280316
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Bilateral trade is a central problem in algorithmic economics, and recent work has explored how to design trading mechanisms using no-regret learning algorithms. However, no-regret learning is impossible when budget balance has to be enforced at each time step. Bernasconi et al. [Ber+24] show how this impossibility can be circumvented by relaxing the budget balance constraint to hold only globally over all time steps. In particular, they design an algorithm achieving regret of the order of $\tilde O(T^{3/4})$ and provide a lower bound of $\Omega(T^{5/7})$. In this work, we interpolate between these two extremes by studying how the optimal regret rate varies with the allowed violation of the global budget balance constraint. Specifically, we design an algorithm that, by violating the constraint by at most $T^{\beta}$ for any given $\beta \in [\frac{3}{4}, \frac{6}{7}]$, attains regret $\tilde O(T^{1 - \beta/3})$. We complement this result with a matching lower bound, thus fully characterizing the trade-off between regret and budget violation. Our results show that both the $\tilde O(T^{3/4})$ upper bound in the global budget balance case and the $\Omega(T^{5/7})$ lower bound under unconstrained budget balance violation obtained by Bernasconi et al. [Ber+24] are tight.
Abstract（参考訳）: 双方向取引はアルゴリズム経済学における中心的な問題であり、近年の研究では、非回帰学習アルゴリズムを用いて取引メカニズムを設計する方法が検討されている。しかし、予算残高を各ステップで実施しなければならない場合、学習の度合は不可能である。 Bernasconi氏ら[Ber+24]は、すべての時間ステップでしか保持できない予算バランスの制約を緩和することで、この不可避性を回避できることを示す。特に、彼らは$\tilde O(T^{3/4})$の順序を後悔するアルゴリズムを設計し、$\Omega(T^{5/7})$の下位境界を提供する。本研究は, この2つの極端を, 世界予算収支の制約に違反した場合に, 最適な後悔率がどのように変化するかを検討することによって補間するものである。具体的には、与えられた$\beta \in [\frac{3}{4}, \frac{6}{7}]$に対して、少なくとも$T^{\beta}$で制約に違反することで、後悔の$\tilde O(T^{1 - \beta/3})$を得るアルゴリズムを設計する。この結果を、一致した低い境界で補うことで、後悔と予算違反のトレードオフを完全に特徴づけます。以上の結果から,大域的予算収支ケースにおける$\tilde O(T^{3/4})$上限と,Bernasconiらによる非拘束的予算収支違反の下での$\Omega(T^{5/7})$下限の両方が厳密であることがわかった。

関連論文リスト

Tight Regret Bounds for Fixed-Price Bilateral Trade [10.237210183229555]
ほぼ最適の$widetildeTheta(T2/3)$ tight bound for $textsfGlobal Budget Balance$ fixed-price mechanism with two-bit/one-bit feedback。相関値/逆値の場合、$Omega(T3/4)$ lower bound for $textsfGlobal Budget Balance$ fixed-price mechanism with two-bit/one-bit feedback。
論文参考訳（メタデータ） (2025-04-06T03:56:42Z)
p-Mean Regret for Stochastic Bandits [52.828710025519996]
単純で統一された UCB ベースのアルゴリズムを導入し、新しい$p$-mean の後悔境界を実現する。我々の枠組みは、特別な場合として、平均的な累積的後悔とナッシュ後悔の両方を包含する。
論文参考訳（メタデータ） (2024-12-14T08:38:26Z)
Adversarial Combinatorial Bandits with Switching Costs [55.2480439325792]
本稿では,各ラウンドで選択したアームのスイッチに対して,切替コストが$lambda$の逆帯域問題について検討する。ミニマックスの後悔とそれにアプローチするための設計アルゴリズムの限界を低くする。
論文参考訳（メタデータ） (2024-04-02T12:15:37Z)
Improved Regret for Bandit Convex Optimization with Delayed Feedback [50.46856739179311]
遅延フィードバックを伴うバンド凸最適化(BCO)。我々は,新しいアルゴリズムを開発し,一般にO(sqrtnT3/4+sqrtdT)$の後悔境界を満足していることを証明する。提案アルゴリズムは,強い凸関数に対して$O((nT)2/3log/3T+dlog T)$に制限された後悔を改善することができることを示す。
論文参考訳（メタデータ） (2024-02-14T13:08:26Z)
Federated Linear Bandits with Finite Adversarial Actions [20.1041278044797]
我々は、M$のクライアントが中央サーバと通信し、線形文脈の帯域幅問題を解決するための連合線形帯域幅モデルについて検討する。逆有限作用集合のユニークな問題に対処するため、FedSupLinUCBアルゴリズムを提案する。我々は、FedSupLinUCBが$tildeO(sqrtd T)$の完全後悔を達成したことを証明している。
論文参考訳（メタデータ） (2023-11-02T03:41:58Z)
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)
Borda Regret Minimization for Generalized Linear Dueling Bandits [65.09919504862496]
本稿では,ボルダスコアが最も高い項目を識別することを目的とした,デュエルバンディットに対するボルダ後悔最小化問題について検討する。本稿では,多くの既存モデルをカバーする一般化線形デュエルバンドモデルのリッチクラスを提案する。我々のアルゴリズムは$tildeO(d2/3 T2/3)$ regretを達成し、これも最適である。
論文参考訳（メタデータ） (2023-03-15T17:59:27Z)
Better Best of Both Worlds Bounds for Bandits with Switching Costs [37.71741656687868]
本稿では,2021年にRouryer,Seldin,Cesa-Bianchiらにより,スイッチングコストを伴うバンディットのベスト・オブ・ザ・ワールドス・アルゴリズムについて検討した。本稿では, 極小最小の最小残差を$mathcalO(T2/3)$で同時に達成する, 驚くほど単純かつ効果的に導入する。
論文参考訳（メタデータ） (2022-06-07T08:22:56Z)
The Best of Both Worlds: Reinforcement Learning with Logarithmic Regret and Policy Switches [84.54669549718075]
漸進的強化学習(RL)における後悔の最小化問題について検討する。一般関数クラスと一般モデルクラスで学ぶことに集中する。対数的後悔境界は$O(log T)$スイッチングコストのアルゴリズムによって実現可能であることを示す。
論文参考訳（メタデータ） (2022-03-03T02:55:55Z)
Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrap [84.66885506098724]
本稿では,アダプティブ・マルチステップ・ブートストラップ (AMB) を用いた表層有限水平マルコフ決定過程 (MDP) のモデルフリーアルゴリズムを提案する。 AMBは,部分最適ギャップの逆の和でのみスケールする,ギャップ依存的後悔境界を達成できることを示す。また、AMB は $frac|Z_mul|Delta_min$ regret という追加の $frac|Z_mul|Delta_min$ を被っていることも示しています。
論文参考訳（メタデータ） (2021-02-09T07:46:34Z)
Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
論文参考訳（メタデータ） (2021-01-20T04:29:18Z)
Near-optimal Regret Bounds for Stochastic Shortest Path [63.029132134792555]
最短経路 (SSP) は計画と制御においてよく知られた問題であり、エージェントは最小の総コストで目標状態に到達する必要がある。任意の学習アルゴリズムは、最悪の場合、少なくとも$Omega(B_star sqrt|S| |A|K)$後悔しなければならない。
論文参考訳（メタデータ） (2020-02-23T09:10:14Z)

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

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