論文の概要: Lookahead identification in adversarial bandits: accuracy and memory bounds
- arxiv url: http://arxiv.org/abs/2603.00803v1
- Date: Sat, 28 Feb 2026 20:38:58 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-03-03 19:50:56.366543
- Title: Lookahead identification in adversarial bandits: accuracy and memory bounds
- Title（参考訳）: 逆行性包帯におけるLookaheadの同定 : 精度とメモリバウンド
- Authors: Nataly Brukhim, Nicolò Cesa-Bianchi, Carlo Ciliberto,
- Abstract要約: マルチアームバンディットにおける識別問題について検討する。
各ラウンドで、学習者はK$の腕のうちの1つを選択し、その報酬を観察する。
過去のパフォーマンスでは、将来についてはほとんど情報を提供しておらず、意味のある識別が可能かどうかという疑問が提起されている。
- 参考スコア（独自算出の注目度）: 24.731657695290227
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study an identification problem in multi-armed bandits. In each round a learner selects one of $K$ arms and observes its reward, with the goal of eventually identifying an arm that will perform best at a {\it future} time. In adversarial environments, however, past performance may offer little information about the future, raising the question of whether meaningful identification is possible at all. In this work, we introduce \emph{lookahead identification}, a task in which the goal of the learner is to select a future prediction window and commit in advance to an arm whose average reward over that window is within $\varepsilon$ of optimal. Our analysis characterizes both the achievable accuracy of lookahead identification and the memory resources required to obtain it. From an accuracy standpoint, for any horizon $T$ we give an algorithm achieving $\varepsilon = O\bigl(1/\sqrt{\log T}\bigr)$ over $Ω(\sqrt{T})$ prediction windows. This demonstrates that, perhaps surprisingly, identification is possible in adversarial settings, despite significant lack of information. We also prove a near-matching lower bound showing that $\varepsilon = Ω\bigl(1/\log T\bigr)$ is unavoidable. We then turn to investigate the role of memory in our problem, first proving that any algorithm achieving nontrivial accuracy requires $Ω(K)$ bits of memory. Under a natural \emph{local sparsity} condition, we show that the same accuracy guarantees can be achieved using only poly-logarithmic memory.
- Abstract（参考訳）: マルチアームバンディットにおける識別問題について検討する。
各ラウンドで、学習者はK$の腕のうちの1つを選択し、その報酬を観察し、最終的には(将来)最高のパフォーマンスの腕を識別する。
しかし、敵対的な環境では、過去のパフォーマンスは将来についてはほとんど情報を提供しておらず、意味のある識別が可能であるかどうかという疑問が提起される。
本研究では,学習者の目標が将来の予測ウィンドウを選択し,そのウィンドウに対する平均報酬が最適な$\varepsilon$以内のアームに前もってコミットするタスクである「emph{lookahead Identification」を紹介する。
本分析では,顔認証の達成可能な精度と,取得に必要な記憶資源の両方を特徴付ける。
精度の観点から、任意の地平線に対して$T$に対して、$\varepsilon = O\bigl(1/\sqrt{\log T}\bigr)$ over$Ω(\sqrt{T})$予測ウィンドウを達成するアルゴリズムを与える。
これは、おそらく意外なことに、情報不足にもかかわらず、敵の設定で識別が可能であることを示している。
また、$\varepsilon = Ω\bigl(1/\log T\bigr)$ が避けられないことを示す、ほぼ一致する下界も証明する。
次に、問題におけるメモリの役割を調査し、まず、非自明な精度を達成するアルゴリズムが$Ω(K)$bitsのメモリを必要とすることを証明した。
自然の \emph{local sparsity} 条件下では、同一の精度保証を多対数メモリのみを用いて達成できることが示される。
関連論文リスト
- Optimal Multi-Objective Best Arm Identification with Fixed Confidence [62.36929749450298]
我々は、各アームが選択時にM$Dのベクトル報酬を得られる多腕バンディット設定を考える。
最終的なゴールは、最も短い(予想される)時間において、エラーの確率の上限に従属する全ての目的の最良のアームを特定することである。
本稿では,各ステップでアームをサンプリングするために,エミュロゲート比例という新しいアイデアを用いたアルゴリズムを提案し,各ステップにおける最大最小最適化問題を解く必要をなくした。
論文 参考訳（メタデータ） (2025-01-23T12:28:09Z) - Fingerprinting Codes Meet Geometry: Improved Lower Bounds for Private Query Release and Adaptive Data Analysis [25.476062424924713]
本稿では,フィンガープリント方式の下位境界の証明のための一般的なフレームワークを提案する。
宇宙上の任意の適応的数え上げクエリにQ$$$mathcalX$ to accuracy $alpha$ needs $Omega(fracsqrt log|mathcalX| log (1/delta) log Qvarepsilonalpha2)$ sample, matching known upper bounds to constants。
論文 参考訳（メタデータ） (2024-12-18T23:11:07Z) - Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits [55.957560311008926]
そこで本研究では,各文脈の平均値によって腕の質を計測するPSLBモデルを提案する。
PS$varepsilon$BAI$+$は、$varepsilon$-optimal armを、確率$ge 1-delta$と最小限のサンプルで識別することが保証される。
論文 参考訳（メタデータ） (2024-10-10T06:15:42Z) - A/B Testing and Best-arm Identification for Linear Bandits with
Robustness to Non-stationarity [28.068960555415014]
非定常環境下での線形包帯の固定予算ベストアーム識別問題について検討する。
アルゴリズムは、可能な限り高い確率で最適な腕 $x* := argmax_xinmathcalXxtopsum_t=1Ttheta_t$ を正しく識別することを目的としている。
論文 参考訳（メタデータ） (2023-07-27T19:03:36Z) - Online Learning with Adversaries: A Differential-Inclusion Analysis [52.43460995467893]
我々は,完全に非同期なオンラインフェデレート学習のための観察行列ベースのフレームワークを提案する。
我々の主な結果は、提案アルゴリズムがほぼ確実に所望の平均$mu.$に収束することである。
新たな差分包摂型2時間スケール解析を用いて,この収束を導出する。
論文 参考訳（メタデータ） (2023-04-04T04:32:29Z) - On the Sample Complexity of Representation Learning in Multi-task
Bandits with Global and Local structure [77.60508571062958]
マルチタスク・バンディット問題に対する最適アーム学習の複雑さについて検討した。
アームは2つのコンポーネントで構成されます。1つはタスク間で共有され(表現と呼ばれます)、もう1つはタスク固有のもの(予測器と呼ばれます)です。
サンプルの複雑さが下界に近づき、最大で$H(Glog(delta_G)+ Xlog(delta_H))$でスケールするアルゴリズムOSRL-SCを考案する。
論文 参考訳（メタデータ） (2022-11-28T08:40:12Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Choosing Answers in $\varepsilon$-Best-Answer Identification for Linear
Bandits [0.8122270502556374]
純粋探索問題では、情報を逐次収集して環境問題に答える。
平均値の高い解を選択すると、期待されるサンプルの複雑さの観点からアルゴリズムが最適に到達できないことを示す。
導出線形帯域における$varepsilon$-best-answer識別にベストアーム識別アルゴリズムを適用するための簡単な手法を開発した。
論文 参考訳（メタデータ） (2022-06-09T12:27:51Z) - There is no Accuracy-Interpretability Tradeoff in Reinforcement Learning
for Mazes [64.05903267230467]
相互理解性は,強化学習システムにおける信頼性に不可欠なビルディングブロックである。
場合によっては、最適性を保ちつつ、政策の解釈可能性を達成することができることを示す。
論文 参考訳（メタデータ） (2022-06-09T04:23:26Z) - On the complexity of All $\varepsilon$-Best Arms Identification [2.1485350418225244]
ガウスの報酬を持つ有限の多腕バンディットにおいて、$varepsilon$-optimal armsを全て識別する問題を考える。
我々は,$varepsilon$-good arms w.h.p の集合を同定し,期待されるサンプルの複雑さの観点から最適性($delta$が 0 になるとき)を享受するトラック・アンド・ストップアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-02-13T10:54:52Z) - Selective Sampling for Online Best-arm Identification [19.767267982167578]
潜在的なオプションのセットが与えられた場合、学習者は1-delta$以上の確率で計算することを目指している。
この研究の主な成果は、ラベル付きサンプルと停止時間の間のトレードオフを正確に特徴づけるものである。
我々のフレームワークは、以前の作業で改善されたバイナリ分類をキャプチャするのに十分な一般性を持っている。
論文 参考訳（メタデータ） (2021-10-28T03:02:08Z) - Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
マルコフ決定過程における純粋探索問題について検討する。
エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
論文 参考訳（メタデータ） (2021-06-05T09:16:28Z) - Probabilistic Sequential Shrinking: A Best Arm Identification Algorithm
for Stochastic Bandits with Corruptions [91.8283876874947]
我々は,T段の固定予算設定において,敵対的腐敗を伴う連続的包帯に対する最適な腕識別(BAI)問題を考察した。
我々は, 汚職の量に依存しない新しいランダム化アルゴリズム, Probabilistic Shrinking($u$) (PSS($u$)) を設計する。
CPS が十分に大きいとき、BAI 確率を$Trightarrow infty$ として達成できるアルゴリズムは存在しない。
論文 参考訳（メタデータ） (2020-10-15T17:34:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。