論文の概要: Tight Regret Bounds for Fixed-Price Bilateral Trade

• arxiv url: http://arxiv.org/abs/2504.04349v1
• Date: Sun, 06 Apr 2025 03:56:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-08 14:09:16.038722
• Title: Tight Regret Bounds for Fixed-Price Bilateral Trade
• Title（参考訳）: 固定価格バイラテラル取引におけるタイトレグレトバウンド
• Authors: Houshuang Chen, Yaonan Jin, Pinyan Lu, Chihao Zhang,
• Abstract要約: ほぼ最適の$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。
• 参考スコア（独自算出の注目度）: 10.237210183229555
• License:
• Abstract: We examine fixed-price mechanisms in bilateral trade through the lens of regret minimization. Our main results are twofold. (i) For independent values, a near-optimal $\widetilde{\Theta}(T^{2/3})$ tight bound for $\textsf{Global Budget Balance}$ fixed-price mechanisms with two-bit/one-bit feedback. (ii) For correlated/adversarial values, a near-optimal $\Omega(T^{3/4})$ lower bound for $\textsf{Global Budget Balance}$ fixed-price mechanisms with two-bit/one-bit feedback, which improves the best known $\Omega(T^{5/7})$ lower bound obtained in the work \cite{BCCF24} and, up to polylogarithmic factors, matches the $\widetilde{\mathcal{O}}(T^{3 / 4})$ upper bound obtained in the same work. Our work in combination with the previous works \cite{CCCFL24mor, CCCFL24jmlr, AFF24, BCCF24} (essentially) gives a thorough understanding of regret minimization for fixed-price bilateral trade. En route, we have developed two technical ingredients that might be of independent interest: (i) A novel algorithmic paradigm, called $\textit{{fractal elimination}}$, to address one-bit feedback and independent values. (ii) A new $\textit{lower-bound construction}$ with novel proof techniques, to address the $\textsf{Global Budget Balance}$ constraint and correlated values.
• Abstract（参考訳）: 両貿易における固定価格機構について, 後悔最小化レンズを用いて検討した。 私たちの主な成果は2倍です。 (i)独立値に対して、ほぼ最適の$\widetilde{\Theta}(T^{2/3})$ tight bound for $\textsf{Global Budget Balance}$ fixed-price mechanism with two-bit/one-bit feedback。 (ii) 相関・逆数値に対して、$\Omega(T^{3/4})$ lower bound for $\textsf{Global Budget Balance}$ fixed-price mechanism with two-bit/one-bit feedback, which improves the best known $\Omega(T^{5/7})$ lower bound obtained in the work \cite{BCCF24} and up to polylogarithmic factors, with the $\widetilde{\mathcal{O}}(T^{3/4})$ upper bound obtained in the work。 我々の研究は、以前の『CCCFL24mor, CCCFL24jmlr, AFF24, BCCF24}』と組み合わせて、固定価格二国間貿易における後悔の最小化について、完全に理解している。 途中、私たちは独立した技術材料を2つ開発しました。 i) 1ビットフィードバックと独立値に対処するため、$\textit{{fractal elimination}}$と呼ばれる新しいアルゴリズムパラダイム。 (ii)新しい$\textit{lower-bound construction}$に新しい証明技法があり、$\textsf{Global Budget Balance}$制約と相関値に対処する。

関連論文リスト

• Contextual Bandits for Unbounded Context Distributions [12.299949253960477]
  非パラメトリックな文脈的包帯は、シーケンシャルな意思決定問題の重要なモデルである。 UCB探査と近接する2つの手法を提案する。 本手法は, 限界条件が弱い場合に, 最小限の後悔を達成できることを示す。 2つ目の方法は、$tildeOleft(T1-frac(alpha+1)betaalpha+(d+2)beta+T1-betaright)$の期待された後悔を達成する。
  論文  参考訳（メタデータ） (2024-08-19T02:30:37Z)
• Linear Contextual Bandits with Hybrid Payoff: Revisited [0.8287206589886881]
  ハイブリッド報酬設定における線形文脈問題について検討する。 この設定では、各アームの報酬モデルには、すべてのアームの報酬モデル間で共有されるパラメータに加えて、アーム固有のパラメータが含まれる。
  論文  参考訳（メタデータ） (2024-06-14T15:41:21Z)
• Adversarial Combinatorial Bandits with Switching Costs [55.2480439325792]
  本稿では,各ラウンドで選択したアームのスイッチに対して,切替コストが$lambda$の逆帯域問題について検討する。 ミニマックスの後悔とそれにアプローチするための設計アルゴリズムの限界を低くする。
  論文  参考訳（メタデータ） (2024-04-02T12:15:37Z)
• Federated Linear Bandits with Finite Adversarial Actions [20.1041278044797]
  我々は、M$のクライアントが中央サーバと通信し、線形文脈の帯域幅問題を解決するための連合線形帯域幅モデルについて検討する。 逆有限作用集合のユニークな問題に対処するため、FedSupLinUCBアルゴリズムを提案する。 我々は、FedSupLinUCBが$tildeO(sqrtd T)$の完全後悔を達成したことを証明している。
  論文  参考訳（メタデータ） (2023-11-02T03:41:58Z)
• Causal Bandits for Linear Structural Equation Models [58.2875460517691]
  本稿では,因果図形モデルにおける最適な介入順序を設計する問題について検討する。 グラフの構造は知られており、ノードは$N$である。 頻繁性(UCBベース)とベイズ的設定に2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-08-26T16:21:31Z)
• Nearly Horizon-Free Offline Reinforcement Learning [97.36751930393245]
  S$状態、$A$アクション、計画的地平$H$で、エピソードな時間同質なMarkov決定プロセスに関するオフライン強化学習を再考する。 経験的MDPを用いた評価と計画のための,約$H$自由なサンプル複雑性境界の最初の集合を得る。
  論文  参考訳（メタデータ） (2021-03-25T18:52:17Z)
• Logarithmic Regret in Feature-based Dynamic Pricing [0.0]
  機能ベースの動的価格設定は、差別化された製品の価格設定の人気が高まっているモデルです。 我々は、インフラクティゲンと敵対的な特徴設定のための2つのアルゴリズムを提供し、両方の最適$O(dlogT)$後悔境界を証明します。 さらに、より一般的な設定で$(sqrtt)$情報理論下限を証明し、"需要曲線の知識"が機能ベースの動的価格の指数関数的な改善につながることを実証します。
  論文  参考訳（メタデータ） (2021-02-20T00:45:33Z)
• 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)
• Adversarial Dueling Bandits [85.14061196945599]
  本稿では,反逆デュエルバンドにおける後悔の問題を紹介する。 学習者は、繰り返し一対のアイテムを選択し、このペアに対する相対的な二項利得フィードバックのみを観察しなければならない。 我々の主な成果は、EmphBorda-winnerの1組の$K$アイテムと比較して、T$ラウンド後悔するアルゴリズムです。
  論文  参考訳（メタデータ） (2020-10-27T19:09:08Z)
• Nearly Optimal Regret for Stochastic Linear Bandits with Heavy-Tailed Payoffs [35.988644745703645]
  我々は、リニアバンディットをヘビーテールのペイオフで分析し、そこではペイオフは1+epsilon$のモーメントしか持たない。 本稿では,$widetildeO(dfrac12Tfrac11+epsilon)$のサブ線形後悔境界を満足する2つの新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-04-28T13:01:38Z)
• Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
  我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。 最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
  論文  参考訳（メタデータ） (2020-03-04T07:36:38Z)

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

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