論文の概要: The Sliding Regret in Stochastic Bandits: Discriminating Index and Randomized Policies

• arxiv url: http://arxiv.org/abs/2311.18437v1
• Date: Thu, 30 Nov 2023 10:37:03 GMT
• ステータス: 処理完了
• システム内更新日: 2023-12-01 17:09:37.034084
• Title: The Sliding Regret in Stochastic Bandits: Discriminating Index and Randomized Policies
• Title（参考訳）: 確率帯域におけるスライディングレグレクト:判別指標とランダム化政策
• Authors: Victor Boone
• Abstract要約: バンディットのためのノンレグレットアルゴリズムのワンショット動作について検討する。 一定長さが無限に滑り落ちるタイムウインドウ上で最悪の擬似回帰を測定するスライディング後悔(slide regret)という新しい概念を導入する。
• 参考スコア（独自算出の注目度）: 0.8158530638728501
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper studies the one-shot behavior of no-regret algorithms for stochastic bandits. Although many algorithms are known to be asymptotically optimal with respect to the expected regret, over a single run, their pseudo-regret seems to follow one of two tendencies: it is either smooth or bumpy. To measure this tendency, we introduce a new notion: the sliding regret, that measures the worst pseudo-regret over a time-window of fixed length sliding to infinity. We show that randomized methods (e.g. Thompson Sampling and MED) have optimal sliding regret, while index policies, although possibly asymptotically optimal for the expected regret, have the worst possible sliding regret under regularity conditions on their index (e.g. UCB, UCB-V, KL-UCB, MOSS, IMED etc.). We further analyze the average bumpiness of the pseudo-regret of index policies via the regret of exploration, that we show to be suboptimal as well.
• Abstract（参考訳）: 本稿では,確率的バンディットに対する非回帰アルゴリズムの一ショット動作について検討する。 多くのアルゴリズムは、予想される後悔に対して漸近的に最適であることが知られているが、単一の実行において、それらの擬似回帰は2つの傾向の1つに従うようだ。 この傾向を測定するために, 一定長さを無限に滑り落ちる時間ウインドウ上で最悪の擬似回帰を測定するスライディング後悔という新しい概念を導入する。 ランダム化法(例えば、トンプソンサンプリング法やMED)は最適な滑り後悔を持つが、インデックスポリシーは、おそらく予想される後悔に対して漸近的に最適であるが、インデックス上の規則性条件(例えば、CB, UCB-V, KL-UCB, MOSS, IMED)下で最悪の滑り後悔を持つことを示す。 さらに,索引政策の疑似回帰の平均的隆起を探索の後悔を通して分析し,さらに亜最適であることを示した。

関連論文リスト

• Thompson Sampling for Infinite-Horizon Discounted Decision Processes [0.0]
  我々はトンプソンサンプリングと呼ばれるサンプリングベースアルゴリズムの挙動を研究する。 標準の(予想された)後悔を分解することで、期待された後悔という新しい尺度を開発します。
  論文  参考訳（メタデータ） (2024-05-14T01:01:05Z)
• 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)
• Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learning [50.44564503645015]
  有限エピソードマルコフ決定過程における強化学習のための改良されたギャップ依存的後悔境界を提供する。 楽観的なアルゴリズムでは,より強い後悔境界を証明し,多数のMDPに対して新たな情報理論的下限を伴う。
  論文  参考訳（メタデータ） (2021-07-02T20:36:05Z)
• High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails [55.561406656549686]
  我々は、勾配推定が末尾を持つ可能性のある一階アルゴリズムを用いたヒルベルト非最適化を考える。 本研究では, 勾配, 運動量, 正規化勾配勾配の収束を高確率臨界点に収束させることと, 円滑な損失に対する最もよく知られた繰り返しを示す。
  論文  参考訳（メタデータ） (2021-06-28T00:17:01Z)
• ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
  第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。 我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。 有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
  論文  参考訳（メタデータ） (2020-08-28T14:46:56Z)
• Lenient Regret for Multi-Armed Bandits [72.56064196252498]
  エージェントが順番に行動を選択し、その行動に対する報酬を観察するマルチアーマッド・バンディット(MAB)問題を考察する。 アルゴリズムの大多数は、後悔、すなわち最高の行動の報酬とエージェントの行動の累積的な差を最小化しようとするが、この基準は望ましくない結果をもたらすかもしれない。 我々は、いくつかの$epsilon$よりも小さな最適性ギャップを無視した、より寛大で寛大で後悔すべき基準を提案する。
  論文  参考訳（メタデータ） (2020-08-10T08:30:52Z)
• Adaptive Discretization for Adversarial Lipschitz Bandits [85.39106976861702]
  リプシッツ・バンディット(Lipschitz bandits)は、大規模で構造化された行動空間を研究する多腕バンディットの顕著なバージョンである。 ここでの中心的なテーマは、アクション空間の適応的な離散化であり、より有望な領域で徐々にズームインする'である。 逆バージョンにおける適応的な離散化のための最初のアルゴリズムを提供し、インスタンス依存の後悔境界を導出する。
  論文  参考訳（メタデータ） (2020-06-22T16:06:25Z)
• Crush Optimism with Pessimism: Structured Bandits Beyond Asymptotic Optimality [25.627939043735683]
  我々は後悔を最小限に抑えるために構造化された包帯について研究する。 本稿では,有限仮説に焦点をあて,有界後悔を楽しみながら最適性を達成できるかを問う。
  論文  参考訳（メタデータ） (2020-06-15T20:46:52Z)
• A General Theory of the Stochastic Linear Bandit and Its Applications [8.071506311915398]
  本稿では,線形バンディット問題に対する一般解析フレームワークとアルゴリズム群を紹介する。 予測における最適化という新たな概念は、OFULの過剰探索問題を減少させるSieeved greedy(SG)と呼ばれる新しいアルゴリズムを生み出します。 SGが理論的に最適であることを示すことに加えて、実験シミュレーションにより、SGはgreedy、OFUL、TSといった既存のベンチマークよりも優れていることが示された。
  論文  参考訳（メタデータ） (2020-02-12T18:54:41Z)
• Thompson Sampling Algorithms for Mean-Variance Bandits [97.43678751629189]
  我々は平均分散MABのためのトンプソンサンプリング型アルゴリズムを開発した。 我々はまた、ガウシアンとベルヌーイの盗賊に対する包括的後悔の分析も提供する。 我々のアルゴリズムは、全てのリスク許容度に対して既存のLCBベースのアルゴリズムを著しく上回っている。
  論文  参考訳（メタデータ） (2020-02-01T15:33:50Z)

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

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