論文の概要: Adaptive Discretization for Adversarial Lipschitz Bandits

• arxiv url: http://arxiv.org/abs/2006.12367v3
• Date: Thu, 12 Aug 2021 17:19:36 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-18 05:38:45.126637
• Title: Adaptive Discretization for Adversarial Lipschitz Bandits
• Title（参考訳）: 逆リプシッツバンドの適応的離散化
• Authors: Chara Podimata, Aleksandrs Slivkins
• Abstract要約: リプシッツ・バンディット(Lipschitz bandits)は、大規模で構造化された行動空間を研究する多腕バンディットの顕著なバージョンである。 ここでの中心的なテーマは、アクション空間の適応的な離散化であり、より有望な領域で徐々にズームインする'である。 逆バージョンにおける適応的な離散化のための最初のアルゴリズムを提供し、インスタンス依存の後悔境界を導出する。
• 参考スコア（独自算出の注目度）: 85.39106976861702
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Lipschitz bandits is a prominent version of multi-armed bandits that studies large, structured action spaces such as the [0,1] interval, where similar actions are guaranteed to have similar rewards. A central theme here is the adaptive discretization of the action space, which gradually ``zooms in'' on the more promising regions thereof. The goal is to take advantage of ``nicer'' problem instances, while retaining near-optimal worst-case performance. While the stochastic version of the problem is well-understood, the general version with adversarial rewards is not. We provide the first algorithm for adaptive discretization in the adversarial version, and derive instance-dependent regret bounds. In particular, we recover the worst-case optimal regret bound for the adversarial version, and the instance-dependent regret bound for the stochastic version. Further, an application of our algorithm to dynamic pricing (where a seller repeatedly adjusts prices for a product) enjoys these regret bounds without any smoothness assumptions.
• Abstract（参考訳）: リプシッツ・バンディット(Lipschitz bandits)は、[0,1]間隔のような大きく構造化された作用空間を研究する多腕バンディットの顕著なバージョンであり、同様の作用が同様の報酬を持つことが保証されている。 ここでの中心的なテーマは、より有望な領域で徐々に ‘zooms in''' となるアクション空間の適応的離散化である。 目標は `nicer'' 問題インスタンスを活用し、最適に近い最悪の場合のパフォーマンスを維持することである。 問題の確率的なバージョンはよく理解されているが、敵の報酬を持つ一般バージョンはそうではない。 逆バージョンにおける適応的な離散化のための最初のアルゴリズムを提供し、インスタンス依存の後悔境界を導出する。 特に, 対数バージョンに対する最悪の最適後悔条件と, 確率バージョンに対するインスタンス依存の後悔条件を回復する。 さらに,このアルゴリズムを動的価格(販売者が商品の価格を繰り返し調整する場合)に適用することで,滑らかさを仮定することなく,これらの後悔の限界を享受できる。

関連論文リスト

• An Adaptive Approach for Infinitely Many-armed Bandits under Generalized Rotting Constraints [29.596684377841182]
  本研究では、休息状態において、アームの平均報酬が各プルで減少する可能性があるが、そうでなければ変化しない、無限に多くの武器を持つバンディット問題を考察する。 本稿では,ゆがみ報酬に起因するバイアスや分散トレードオフを管理するために,適応的なスライディングウィンドウを備えたUTBを利用するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-04-22T14:11:54Z)
• $(\epsilon, u)$-Adaptive Regret Minimization in Heavy-Tailed Bandits [29.966828248335972]
  我々は,学習者に対して,$epsilon$と$u$が不明な場合に,後悔の最小化問題を調査する。 AdaR-UCBは、適応しない重みを帯びたケースとほぼ一致した後悔の保証を享受する最初のアルゴリズムである。
  論文  参考訳（メタデータ） (2023-10-04T17:11:15Z)
• Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
  本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。 本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。 我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
  論文  参考訳（メタデータ） (2023-10-02T08:15:52Z)
• Invariant Lipschitz Bandits: A Side Observation Approach [18.688474183114085]
  不変リプシッツ・バンディット・セッティング (invariant Lipschitz bandit set) について検討し、報酬関数と腕の集合を変換群の下で保存する。 我々は、グループ軌道を用いた側面観測を自然に統合する textttUniformMesh-N というアルゴリズムを導入する。 我々は、群が有限であることを考えると、群の濃度に依存するような改善された後悔の上界を証明する。
  論文  参考訳（メタデータ） (2022-12-14T22:12:32Z)
• Contextual Bandits with Smooth Regret: Efficient Learning in Continuous Action Spaces [14.366265951396587]
  我々は、大規模または連続的なアクション空間に対する効率的な汎用的コンテキスト帯域幅アルゴリズムを設計する。 本稿では,従来提案されていた代替案に支配的な文脈的包帯に対して,スムーズな後悔の念を抱く概念を提案する。 我々のアルゴリズムは、標準的な後悔の下で以前のminimax/Paretoの最適保証を回復するために使用することができる。
  論文  参考訳（メタデータ） (2022-07-12T21:27:09Z)
• Minimax Optimal Quantile and Semi-Adversarial Regret via Root-Logarithmic Regularizers [31.102181563065844]
  量子的(そしてより一般的には、KL)後悔は、最高の個人専門家と競争する目標を緩和し、敵対的なデータに関して、ほとんどの専門家と競争するだけである。 最近では、半対人パラダイム(Bilodeau、Negrea、Roy 2020)は、完全に対人的でも対人的でもないデータを考えることによって、対人的オンライン学習の代替緩和を提供する。 我々は、FTRLと別個のルート対数正規化器を併用したFTRLを用いて、両方のパラダイムにおいて最小限の後悔を達成し、どちらも正規Hedgeの変種と解釈できる。
  論文  参考訳（メタデータ） (2021-10-27T22:38:52Z)
• Anti-Concentrated Confidence Bonuses for Scalable Exploration [57.91943847134011]
  固有の報酬は、探検と探検のトレードオフを扱う上で中心的な役割を果たす。 楕円ボーナスを効率的に近似するためのエンファンティ集中型信頼境界を導入する。 我々は,Atariベンチマーク上での現代固有の報酬と競合する,深層強化学習のための実用的な変種を開発する。
  論文  参考訳（メタデータ） (2021-10-21T15:25:15Z)
• Bias-Robust Bayesian Optimization via Dueling Bandit [57.82422045437126]
  ベイジアン最適化は、観測が逆偏りとなるような環境において考慮する。 情報指向サンプリング(IDS)に基づくダリングバンディットの新しい手法を提案する。 これにより、累積的後悔保証を伴う帯域幅の並列化のための、最初の効率的なカーネル化アルゴリズムが得られる。
  論文  参考訳（メタデータ） (2021-05-25T10:08:41Z)
• Lenient Regret for Multi-Armed Bandits [72.56064196252498]
  エージェントが順番に行動を選択し、その行動に対する報酬を観察するマルチアーマッド・バンディット(MAB)問題を考察する。 アルゴリズムの大多数は、後悔、すなわち最高の行動の報酬とエージェントの行動の累積的な差を最小化しようとするが、この基準は望ましくない結果をもたらすかもしれない。 我々は、いくつかの$epsilon$よりも小さな最適性ギャップを無視した、より寛大で寛大で後悔すべき基準を提案する。
  論文  参考訳（メタデータ） (2020-08-10T08:30:52Z)
• Stochastic Linear Bandits Robust to Adversarial Attacks [117.665995707568]
  我々はロバスト位相除去アルゴリズムの2つの変種を提供し、その1つは$C$を知っており、もう1つはそうでない。 いずれの変種も、倒壊しない場合には、それぞれ$C = 0$ となり、それぞれ追加の加法項が生じる。 文脈的設定では、単純な欲求的アルゴリズムは、明示的な探索を行わず、C$を知らないにもかかわらず、ほぼ最適加法的後悔項で証明可能な堅牢性を示す。
  論文  参考訳（メタデータ） (2020-07-07T09:00:57Z)

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

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