論文の概要: $k\texttt{-experts}$ -- Online Policies and Fundamental Limits
- arxiv url: http://arxiv.org/abs/2110.07881v1
- Date: Fri, 15 Oct 2021 06:30:15 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-18 15:16:48.841205
- Title: $k\texttt{-experts}$ -- Online Policies and Fundamental Limits
- Title（参考訳）: k\texttt{-experts}$ -- オンラインポリシーと基本的な制限
- Authors: Samrat Mukhopadhyay, Sourav Sahoo, Abhishek Sinha
- Abstract要約: 本稿では,textttExperts$問題について検討する。
学習者は各ラウンドで$k$のエキスパートのサブセットをN$のエキスパートのプールから選択する。
任意のラウンドで学習者が得られる報酬は、選択した専門家の報酬に依存する。
- 参考スコア（独自算出の注目度）: 8.84337023214151
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: This paper introduces and studies the $k\texttt{-experts}$ problem -- a
generalization of the classic Prediction with Expert's Advice (i.e., the
$\texttt{Experts}$) problem. Unlike the $\texttt{Experts}$ problem, where the
learner chooses exactly one expert, in this problem, the learner selects a
subset of $k$ experts from a pool of $N$ experts at each round. The reward
obtained by the learner at any round depends on the rewards of the selected
experts. The $k\texttt{-experts}$ problem arises in many practical settings,
including online ad placements, personalized news recommendations, and paging.
Our primary goal is to design an online learning policy having a small regret.
In this pursuit, we propose $\texttt{SAGE}$ ($\textbf{Sa}$mpled
Hed$\textbf{ge}$) - a framework for designing efficient online learning
policies by leveraging statistical sampling techniques. We show that, for many
related problems, $\texttt{SAGE}$ improves upon the state-of-the-art bounds for
regret and computational complexity. Furthermore, going beyond the notion of
regret, we characterize the mistake bounds achievable by online learning
policies for a class of stable loss functions. We conclude the paper by
establishing a tight regret lower bound for a variant of the
$k\texttt{-experts}$ problem and carrying out experiments with standard
datasets.
- Abstract（参考訳）: 本稿では、$k\textt{-experts}$ problem -- エキスパートのアドバイスによる古典的な予測(つまり、$\textt{Experts}$)問題の一般化を紹介し、研究する。
この問題は、学習者がちょうど1人の専門家を選ぶ$\texttt{experts}$問題とは異なり、学習者は各ラウンドの1ドルの専門家のプールから、$k$のエキスパートのサブセットを選択する。
任意のラウンドで学習者が得られる報酬は、選ばれた専門家の報酬に依存する。
k\texttt{-experts}$問題は、オンライン広告の配置、パーソナライズされたニュースレコメンデーション、ページングなど、多くの実践的な設定で発生する。
私たちの主な目標は、小さな後悔を持つオンライン学習ポリシーを設計することです。
本稿では,統計的サンプリング技術を利用して効率的なオンライン学習ポリシーを設計するためのフレームワークである$\texttt{SAGE}$$$$\textbf{Sa}$mpled Hed$\textbf{ge}$)を提案する。
多くの関連する問題に対して、$\texttt{sage}$ は、後悔と計算の複雑さに対する最先端の境界を改善している。
さらに、後悔の概念を超えて、安定した損失関数のクラスに対するオンライン学習ポリシーによって達成可能な誤りを特徴づける。
論文の結論は、$k\texttt{-experts}$問題に対する厳密な後悔の下限を確立し、標準データセットを用いた実験を行うことである。
関連論文リスト
- No-Regret Online Prediction with Strategic Experts [16.54912614895861]
オンラインバイナリ予測の一般化をエキスパートアドバイスフレームワークを用いて研究し、各ラウンドで、学習者は、Kドルの専門家のプールからmgeq 1ドルの専門家を選ぶことができる。
我々は、専門家が戦略的に行動し、彼らの信念を誤報することでアルゴリズムの予測への影響を最大化することを目的とした設定に焦点を当てる。
目標は,次の2つの要件を満たすアルゴリズムを設計することです。 1) $textitIncentive-compatible$: 専門家に信念を真実に報告させるインセンティブ,2) $textitNo-regret$: Achieve。
論文 参考訳（メタデータ） (2023-05-24T16:43:21Z) - Non-stationary Projection-free Online Learning with Dynamic and Adaptive
Regret Guarantees [36.746745619968024]
本研究では,非定常プロジェクションフリーオンライン学習について検討し,動的後悔と適応的後悔を選択して評価を行った。
我々の結果は、プロジェクションフリーオンライン学習における最初の一般的な動的後悔境界であり、既存の$mathcalO(T3/4)$static regretを復元することができる。
本稿では,$tildemathcalO(tau3/4)$ アダプティブリフレッシュバウンドを長さ$tauの任意の間隔で達成するためのプロジェクションフリーな手法を提案する。
論文 参考訳（メタデータ） (2023-05-19T15:02:10Z) - 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) - Private Online Prediction from Experts: Separations and Faster Rates [74.52487417350221]
専門家によるオンライン予測は機械学習の基本的な問題であり、いくつかの研究がプライバシーの制約の下でこの問題を研究している。
本研究では,非適応的敵に対する最良な既存アルゴリズムの残差を克服する新たなアルゴリズムを提案し,解析する。
論文 参考訳（メタデータ） (2022-10-24T18:40:19Z) - Efficient and Optimal Fixed-Time Regret with Two Experts [5.650647159993238]
専門家のアドバイスによる予測は、オンライン学習における基礎的な問題である。
T$のラウンドと$n$のエキスパートを持つ場合、古典的な乗法的重み更新法は、$T$が事前に知られているときに、少なくとも$sqrt(T/2)ln n$の後悔を被る。
専門家が$n$の数が小さい/固定された場合、より後悔する保証のあるアルゴリズムが存在する。
論文 参考訳（メタデータ） (2022-03-15T01:07:09Z) - Online Selective Classification with Limited Feedback [82.68009460301585]
オンライン学習モデルにおいて、予測者がインスタンスの分類を控える可能性のある選択的分類について検討する。
私たちが考慮している設定の健全な2つの側面は、データが不可避である可能性があるため、データは不可避である可能性があるということです。
smash$tildeO(T1-mu)$ over abstention against Adaptive adversaries. smash$tildeO(T1-mu)$ incurring smash$tildeO(T1-mu)$ over abstention。
論文 参考訳（メタデータ） (2021-10-27T08:00:53Z) - Nonstochastic Bandits with Infinitely Many Experts [1.7188280334580197]
無限に多くの専門家と非確率的盗賊の問題を考察する。
有限個の専門家に対して、正しい専門家ランキングの推測を可能にするExp4.Pの変種を提案する。
そして、この変種を無限に多くの専門家に作用するメタアルゴリズムに組み込む。
論文 参考訳（メタデータ） (2021-02-09T22:42:36Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z) - Toward Optimal Adversarial Policies in the Multiplicative Learning
System with a Malicious Expert [87.12201611818698]
専門家のアドバイスを組み合わせて真の結果を予測する学習システムについて考察する。
専門家の一人が悪意があり、システムに最大損失を課すことを目指していると推測されている。
誤予測を常に報告する単純な欲求ポリシーは、近似比が1+O(sqrtfracln NN)$で最適であることを示す。
悪意のある専門家がその判断を適応的に行うことができるオンライン環境では、最適のオンラインポリシーを$O(N3)$で動的プログラムを解くことで効率的に計算できることが示される。
論文 参考訳（メタデータ） (2020-01-02T18:04:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。