論文の概要: Is Online Linear Optimization Sufficient for Strategic Robustness?
- arxiv url: http://arxiv.org/abs/2602.12253v1
- Date: Thu, 12 Feb 2026 18:41:55 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-02-13 21:07:25.983777
- Title: Is Online Linear Optimization Sufficient for Strategic Robustness?
- Title（参考訳）: オンライン線形最適化は戦略的ロバスト性に十分か?
- Authors: Yang Cai, Haipeng Luo, Chen-Yu Wei, Weiqiang Zheng,
- Abstract要約: no-swap-regretアルゴリズムは望ましい特性の両方を達成するが、統計的および計算効率の面では最適ではない。
オンライン勾配上昇は、O(sqrtTK)$ 後悔と戦略的堅牢性を達成する唯一のアルゴリズムである。
我々は,任意のOLOアルゴリズムを戦略的にロバストなノンレグレット入札アルゴリズムに変換する,単純なブラックボックス削減を構築する。
- 参考スコア（独自算出の注目度）: 54.49053278073321
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider bidding in repeated Bayesian first-price auctions. Bidding algorithms that achieve optimal regret have been extensively studied, but their strategic robustness to the seller's manipulation remains relatively underexplored. Bidding algorithms based on no-swap-regret algorithms achieve both desirable properties, but are suboptimal in terms of statistical and computational efficiency. In contrast, online gradient ascent is the only algorithm that achieves $O(\sqrt{TK})$ regret and strategic robustness [KSS24], where $T$ denotes the number of auctions and $K$ the number of bids. In this paper, we explore whether simple online linear optimization (OLO) algorithms suffice for bidding algorithms with both desirable properties. Our main result shows that sublinear linearized regret is sufficient for strategic robustness. Specifically, we construct simple black-box reductions that convert any OLO algorithm into a strategically robust no-regret bidding algorithm, in both known and unknown value distribution settings. For the known value distribution case, our reduction yields a bidding algorithm that achieves $O(\sqrt{T \log K})$ regret and strategic robustness (with exponential improvement on the $K$-dependence compared to [KSS24]). For the unknown value distribution case, our reduction gives a bidding algorithm with high-probability $O(\sqrt{T (\log K+\log(T/δ)})$ regret and strategic robustness, while removing the bounded density assumption made in [KSS24].
- Abstract（参考訳）: ベイズ第一価格オークションの競売について検討する。
最適な後悔を達成するバイディングアルゴリズムは広く研究されてきたが、売り手の操作に対する戦略的堅牢性はいまだに未熟である。
no-swap-regretアルゴリズムに基づくバイディングアルゴリズムは、望ましい特性の両方を達成するが、統計的および計算効率の面では最適ではない。
対照的に、オンライン勾配上昇は、$O(\sqrt{TK})$後悔と戦略的堅牢性[KSS24]を達成する唯一のアルゴリズムであり、$T$はオークションの数を表し、$K$は入札数を表す。
本稿では,単純なオンライン線形最適化(OLO)アルゴリズムが,双方の望ましい特性を持つ入札アルゴリズムに十分であるかどうかを考察する。
本研究の主な成果は, 線形線形化後悔は戦略的堅牢性に十分であることを示す。
具体的には、任意のOLOアルゴリズムを、未知の値分布設定と未知の値分布設定の両方において、戦略的に堅牢な非回帰入札アルゴリズムに変換する単純なブラックボックス削減を構築する。
既知の値分布の場合、我々の還元は$O(\sqrt{T \log K})$後悔と戦略的堅牢性を達成する入札アルゴリズムをもたらす([KSS24]と比較して、$K$-dependenceを指数関数的に改善する)。
未知の値分布の場合、我々は高確率の$O(\sqrt{T (\log K+\log(T/δ)})$ 後悔と戦略的堅牢性を持ち、[KSS24]の有界密度仮定を除去する。
関連論文リスト
- Optimal and Practical Batched Linear Bandit Algorithm [8.087699764574788]
本稿では, 線形バンドイット問題(バッチ化線形バンドイット)について, 限定適応性の下で検討する。
我々は,腕の除去と正規化G-最適設計を統合した新しいバッチアルゴリズムBLAEを提案する。
BLAEは、全てのレジームにおける証明可能なミニマックス最適性と、バッチ化された線形帯域における実用上の優位性を組み合わせた最初のアルゴリズムである。
論文 参考訳（メタデータ） (2025-07-11T09:29:28Z) - Indexed Minimum Empirical Divergence-Based Algorithms for Linear Bandits [55.938644481736446]
Indexed Minimum Empirical Divergence (IMED)は、マルチアームバンディット問題に対する非常に効果的なアプローチである。
UCBベースのアルゴリズムとトンプソンサンプリングを実証的に上回ることが観察されている。
我々は、LinIMEDアルゴリズムのファミリーと呼ぶIMEDアルゴリズムの新しい線形バージョンを提案する。
論文 参考訳（メタデータ） (2024-05-24T04:11:58Z) - Strategically-Robust Learning Algorithms for Bidding in First-Price Auctions [11.988955088595858]
ゲーム理論と機械学習のインターフェースにおいて,プライスオークションを繰り返し競うことの学習は基本的な問題である。
本稿では,プライスオークションにおける純ストラテジー入札のための新しいコンケーブの定式化を提案し,この問題に対する自然なグラディエント・アセンセント・アルゴリズムの解析に利用した。
論文 参考訳（メタデータ） (2024-02-12T01:33:33Z) - Safe Online Bid Optimization with Return-On-Investment and Budget
Constraints subject to Uncertainty [87.81197574939355]
最適化問題と学習問題の両方について検討する。
我々は、潜在的に線形な数の制約違反を犠牲にして、サブ線形後悔を保証するアルゴリズム、すなわちGCBを提供する。
より興味深いことに、我々はGCB_safe(psi,phi)というアルゴリズムを提供し、サブ線形擬似回帰と安全性w.h.p.の両方を、耐性 psi と phi を受け入れるコストで保証する。
論文 参考訳（メタデータ） (2022-01-18T17:24:20Z) - Misspecified Gaussian Process Bandit Optimization [59.30399661155574]
カーネル化されたバンディットアルゴリズムは、この問題に対して強い経験的および理論的性能を示した。
本稿では、未知関数を$epsilon$-一様近似で近似できるエンフェミス特定カーネル化帯域設定を、ある再生カーネルヒルベルト空間(RKHS)において有界ノルムを持つ関数で導入する。
提案アルゴリズムは,不特定性に関する事前知識を伴わず,$epsilon$への最適依存を実現する。
論文 参考訳（メタデータ） (2021-11-09T09:00:02Z) - Regret Lower Bound and Optimal Algorithm for High-Dimensional Contextual
Linear Bandit [10.604939762790517]
我々は、累積後悔に対して、$mathcalObig((log d)fracalpha+12Tfrac1-alpha2+log Tbig)$をミニマックス下界として証明する。
第2に,汎用的なアッパー信頼境界(UCB)戦略に着想を得た,シンプルで効率的なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-09-23T19:35:38Z) - Byzantine-Resilient Non-Convex Stochastic Gradient Descent [61.6382287971982]
敵対的レジリエントな分散最適化。
機械は独立して勾配を計算し 協力することができます
私達のアルゴリズムは新しい集中の技術およびサンプル複雑性に基づいています。
それは非常に実用的です:それはないときすべての前の方法の性能を改善します。
セッティングマシンがあります。
論文 参考訳（メタデータ） (2020-12-28T17:19:32Z) - Efficient Algorithms for Stochastic Repeated Second-price Auctions [0.0]
我々は,繰り返し競売を行うための効率的な逐次入札戦略を開発する。
この問題に対する最初のパラメトリック下界を提供する。
本稿では,探索時コミット帯域幅アルゴリズムを思い起こさせる,より説明可能な戦略を提案する。
論文 参考訳（メタデータ） (2020-11-10T12:45:02Z) - Large-Scale Methods for Distributionally Robust Optimization [53.98643772533416]
我々のアルゴリズムは、トレーニングセットのサイズとパラメータの数によらず、多くの評価勾配を必要とすることを証明している。
MNIST と ImageNet の実験により,本手法の 9-36 倍の効率性を持つアルゴリズムの理論的スケーリングが確認された。
論文 参考訳（メタデータ） (2020-10-12T17:41:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。