論文の概要: Toward Optimal Regret in Robust Pricing: Decoupling Corruption and Time
- arxiv url: http://arxiv.org/abs/2605.08290v1
- Date: Fri, 08 May 2026 08:22:43 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-05-12 23:28:49.536652
- Title: Toward Optimal Regret in Robust Pricing: Decoupling Corruption and Time
- Title（参考訳）: ロバスト価格の最適回帰に向けて:破壊と時間の分離
- Authors: Kalana Kalupahana, Francesco Emanuele Stradi, Matteo Castiglioni, Alberto Marchesi,
- Abstract要約: 汚い$C$が分かっていれば$mathcalO(C+log2 T)$、汚い$C$が不明であれば$mathcalO(C+log2 T)$。
- 参考スコア（独自算出の注目度）: 26.424688112476378
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We design the first regret guarantees for robust dynamic pricing that decouple the dependence on the corruption $C$ and the time horizon $T$. In dynamic pricing, a seller with unlimited supply of a good interacts with a stream of buyers over \( T \) rounds, with the goal of maximizing revenue. At each round $t$, the seller posts a price $p_t$, and the buyer purchases the good only if their unknown valuation $v^\star$ exceeds this price. The seller observes only the binary feedback $\mathbb{I} \left\{ p_t \leq v^\star \right\}$, indicating whether a sale occurred. In the \emph{robust} pricing setting, a malicious adversary is allowed to corrupt this feedback in at most $C$ rounds. Even if the learner knows the corruption $C$, the best known regret bound is $\mathcal{O}(C\log\log T)$ by Gupta et al. [2025]. This leaves as an open problem to ``decouple'' the dependence on $C$ and $T$. In this work, we resolve this open problem. In particular, we develop a robust variant of binary search that achieves regret $\mathcal{O}(C+\log T)$ when the corruption $C$ is known and $\mathcal{O}(C+\log^2 T)$ when the corruption is unknown.
- Abstract（参考訳）: 我々は、汚職$C$と時間軸$T$への依存を分離する堅牢な動的価格に関する最初の後悔の保証を設計する。
動的価格設定では、良い商品を無制限に供給する売り手は、(T \)ラウンドで購入者のストリームとやり取りし、収益を最大化する。
各ラウンドの$t$で、売り手は$p_t$を投稿し、買い手は、未知のバリュエーション$v^\star$がこの価格を超える場合にのみ商品を購入する。
売り手はバイナリフィードバック $\mathbb{I} \left\{ p_t \leq v^\star \right\}$ のみを観察し、販売が行われたかどうかを示す。
emph{robust}の価格設定では、悪意のある敵は、このフィードバックを少なくとも$C$ラウンドで不正にすることができる。
学習者が$C$を知っていても、最もよく知られた後悔境界はGuptaらによる$\mathcal{O}(C\log\log T)$である。
これはオープンな問題として、$C$と$T$に依存する ``decouple'' に残される。
この作業では、このオープンな問題を解決します。
特に、汚い$C$と汚い$\mathcal{O}(C+\log^2T)が分かっていれば、後悔する$\mathcal{O}(C+\log T)$と汚い$\mathcal{O}(C+\log^2T)$を達成できる二分探索の堅牢な変種を開発する。
関連論文リスト
- Better Bounds for the Distributed Experts Problem [69.88181841362488]
我々は分散専門家の問題を調査し、$n$の専門家が$s$サーバに分散して$T$タイムステップを提供する。
約$Rgtrsimfrac1sqrtTcdottextpolylog(nsT)$, using $mathcalOleft(fracnR2+fracsR2right)cdotmax(s1-2/p, 1)cdottextpolylog(nsT)$
論文 参考訳（メタデータ） (2026-03-10T04:17:34Z) - Contextual Online Bilateral Trade [18.8734045754182]
我々は、貿易と利益の2つの目的について研究する。
我々は、取引の利益のために$O(dlog d)$後悔するアルゴリズムを設計し、利益のために$O(dlog T + dlog d)$後悔するアルゴリズムを設計する。
論文 参考訳（メタデータ） (2026-02-13T13:03:10Z) - Unconstrained Robust Online Convex Optimization [38.9652176513385]
私たちは、アルゴリズムが低い後悔を保たなければならないという困難な「制約のない」設定に焦点を合わせます。
我々のアルゴリズムは、$G ge max_t |g_t|$ が知られているときに |u|G (sqrtT + k) $ を許す。
論文 参考訳（メタデータ） (2025-06-15T09:21:15Z) - Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback [49.84060509296641]
オンライン有限水平マルコフ決定過程を逆向きに変化した損失と総括的帯域幅フィードバック(フルバンド幅)を用いて研究する。
この種のフィードバックの下では、エージェントは、軌跡内の各中間段階における個々の損失よりも、軌跡全体に生じる総損失のみを観察する。
この設定のための最初のポリシー最適化アルゴリズムを紹介します。
論文 参考訳（メタデータ） (2025-02-06T12:03:24Z) - Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback [58.66941279460248]
人からのフィードバックから学ぶことは、大言語モデル(LLM)のような生成モデルを調整する上で重要な役割を果たす
本稿では,このドメイン内のモデルについて考察する。-文脈的デュエルバンディット(contextual dueling bandits)と,正の選好ラベルを相手によって反転させることができる対向フィードバック(reversarial feedback)について考察する。
本稿では,不確実性重み付き最大推定に基づく頑健なコンテキストデュエルバンドイット(RCDB)を提案する。
論文 参考訳（メタデータ） (2024-04-16T17:59:55Z) - 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) - Density-Based Algorithms for Corruption-Robust Contextual Search and Convex Optimization [21.287905447745953]
対向雑音モデルにおいて、高次元における二項探索の一般化である文脈探索の問題を考察する。
我々は$epsilon$-ballと絶対的な損失に焦点を当てている。
論文 参考訳（メタデータ） (2022-06-15T13:18:52Z) - Logarithmic Regret from Sublinear Hints [76.87432703516942]
自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。
また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
論文 参考訳（メタデータ） (2021-11-09T16:50:18Z) - Improved Analysis of Robustness of the Tsallis-INF Algorithm to
Adversarial Corruptions in Stochastic Multiarmed Bandits [12.462608802359936]
Zimmert and Seldin (2021) の Tsallis-INF アルゴリズムに対する後悔の境界を改善した。
特に、$C = Thetaleft(fracTlog Tlog T$)$の場合、$T$が時空である場合、乗算因子による改善を達成します。
また, time horizon 上の後悔の依存性を $log t$ から $log frac(k-1)t(sum_ineq i*frac1delta_ に改善する。
論文 参考訳（メタデータ） (2021-03-23T12:26:39Z) - Logarithmic Regret in Feature-based Dynamic Pricing [0.0]
機能ベースの動的価格設定は、差別化された製品の価格設定の人気が高まっているモデルです。
我々は、インフラクティゲンと敵対的な特徴設定のための2つのアルゴリズムを提供し、両方の最適$O(dlogT)$後悔境界を証明します。
さらに、より一般的な設定で$(sqrtt)$情報理論下限を証明し、"需要曲線の知識"が機能ベースの動的価格の指数関数的な改善につながることを実証します。
論文 参考訳（メタデータ） (2021-02-20T00:45:33Z) - Adversarial Dueling Bandits [85.14061196945599]
本稿では,反逆デュエルバンドにおける後悔の問題を紹介する。
学習者は、繰り返し一対のアイテムを選択し、このペアに対する相対的な二項利得フィードバックのみを観察しなければならない。
我々の主な成果は、EmphBorda-winnerの1組の$K$アイテムと比較して、T$ラウンド後悔するアルゴリズムです。
論文 参考訳（メタデータ） (2020-10-27T19:09:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。