論文の概要: Nonstochastic Bandits with Infinitely Many Experts
- arxiv url: http://arxiv.org/abs/2102.05164v1
- Date: Tue, 9 Feb 2021 22:42:36 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-11 14:46:24.738571
- Title: Nonstochastic Bandits with Infinitely Many Experts
- Title（参考訳）: 無限に多くの専門家を持つ非確率的バンド
- Authors: X. Flora Meng, Tuhin Sarkar, Munther A. Dahleh
- Abstract要約: 無限に多くの専門家と非確率的盗賊の問題を考察する。
有限個の専門家に対して、正しい専門家ランキングの推測を可能にするExp4.Pの変種を提案する。
そして、この変種を無限に多くの専門家に作用するメタアルゴリズムに組み込む。
- 参考スコア（独自算出の注目度）: 1.7188280334580197
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of nonstochastic bandits with infinitely many experts: A
learner aims to maximize the total reward by taking actions sequentially based
on bandit feedback while benchmarking against a countably infinite set of
experts. We propose a variant of Exp4.P that, for finitely many experts,
enables inference of correct expert rankings while preserving the order of the
regret upper bound. We then incorporate the variant into a meta-algorithm that
works on infinitely many experts. We prove a high-probability upper bound of
$\tilde{\mathcal{O}} \big( i^*K + \sqrt{KT} \big)$ on the regret, up to polylog
factors, where $i^*$ is the unknown position of the best expert, $K$ is the
number of actions, and $T$ is the time horizon. We also provide an example of
structured experts and discuss how to expedite learning in such case. Our
meta-learning algorithm achieves the tightest regret upper bound for the
setting considered when $i^* = \tilde{\mathcal{O}} \big( \sqrt{T/K} \big)$. If
a prior distribution is assumed to exist for $i^*$, the probability of
satisfying a tight regret bound increases with $T$, the rate of which can be
fast.
- Abstract（参考訳）: 学習者は、数え切れないほどの専門家集団に対してベンチマークを行いながら、バンディットフィードバックに基づいて順次行動することで、総報酬を最大化することを目的としています。
有限個の専門家に対して,後悔の上位値の順序を維持しつつ,正しいエキスパートランキングの推測を可能にするexp4.pの変種を提案する。
そして、この変種を無限に多くの専門家に作用するメタアルゴリズムに組み込む。
我々は、$\tilde{\mathcal{O}} \big(i^*K + \sqrt{KT} \big)$の高確率上限を後悔して、$i^*$が最高の専門家の未知の位置であり、$K$がアクションの数であり、$T$が時間の地平線であるポリログ要因まで証明します。
また,構造化専門家の例を示し,そのような場合の学習の迅速化について論じる。
我々のメタラーニングアルゴリズムは、$i^* = \tilde{\mathcal{O}} \big( \sqrt{T/K} \big)$とみなす設定に対して最も厳しい後悔の上限を達成する。
先行分布が$i^*$で存在すると仮定すると、厳密な後悔境界を満たす確率は$T$と増加し、その確率は速くなる。
関連論文リスト
- Improved Regret Bounds for Bandits with Expert Advice [16.699381591572163]
我々は、最悪のケースの後悔に対して$sqrtK T ln(N/K)$の下位境界を証明し、そこでは$K$はアクションの数、$N>K$はエキスパートの数、$T$はタイムホライズである。
これは、前述した同じ順序の上界と一致し、$sqrtK T (ln N) / (ln K)$の最良の下界を改善する。
論文 参考訳（メタデータ） (2024-06-24T17:14:31Z) - Near-optimal Per-Action Regret Bounds for Sleeping Bandits [8.261117235807607]
睡眠中の包帯に対して, 行動毎のほぼ最適な後悔境界を導出する。
合計で$K$、最大で$A$の武器が各ラウンドで$T$以上の場合、最もよく知られている上限は$O(KsqrtTAlnK)$である。
本研究は睡眠専門家のアドバイスで盗賊の設定まで拡張し,その過程でEXP4を一般化する。
論文 参考訳（メタデータ） (2024-03-02T21:22:46Z) - Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs [72.40181882916089]
我々のアルゴリズムが $tildeObig((d+log (|mathcalS|2 |mathcalA|))sqrtKbig)$ regret with full-information feedback, where $d$ is the dimension of a known feature mapping is linearly parametrizing the unknown transition kernel of the MDP, $K$ is the number of episodes, $|mathcalS|$ and $|mathcalA|$ is the standardities of the state and action space。
論文 参考訳（メタデータ） (2023-05-15T05:37:32Z) - Streaming Algorithms for Learning with Experts: Deterministic Versus
Robust [62.98860182111096]
エキスパート問題を伴うオンライン学習では、アルゴリズムは、T$day(または時間)ごとに結果を予測する必要がある。
目標は最小限のコストで予測を行うことだ。
最良専門家が$M$の誤りを犯したとき、後悔する$R$を達成するような決定論的アルゴリズムに対して、$widetildeOmegaleft(fracnMRTright)$の空間下界を示す。
論文 参考訳（メタデータ） (2023-03-03T04:39:53Z) - Constant regret for sequence prediction with limited advice [0.0]
予測とm$ge$2の専門家の損失を観測するために,p = 2の専門家のみを1ラウンド毎に組み合わせた戦略を提供する。
学習者が1ラウンドにつき1人の専門家のフィードバックのみを観察することを制約されている場合、最悪の場合の後悔は"スローレート"$Omega$($sqrt$KT)である。
論文 参考訳（メタデータ） (2022-10-05T13:32:49Z) - Bandits with Stochastic Experts: Constant Regret, Empirical Experts and Episodes [36.104981594178525]
エージェントが一連の専門家ポリシーを介し介入できる文脈的帯域幅問題の変種について検討する。
本稿では,D-UCB(Divergence-based Upper Confidence Bound)アルゴリズムを提案する。
また,経験的D-UCB (ED-UCB) アルゴリズムも提案する。
論文 参考訳（メタデータ） (2021-07-07T14:58:14Z) - Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits
with Linear Payoff Functions [53.77572276969548]
我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。
一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-20T04:29:18Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z) - Improved Sleeping Bandits with Stochastic Actions Sets and Adversarial
Rewards [59.559028338399855]
我々は,行動セットと敵意の報酬を伴って睡眠中の盗賊の問題を考察する。
本稿では,EXP3にインスパイアされた新しい計算効率のよいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-04-14T00:41:26Z) - Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。
最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
論文 参考訳（メタデータ） (2020-03-04T07:36:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。