論文の概要: Information-Theoretic Regret Bounds for Bandits with Fixed Expert Advice
- arxiv url: http://arxiv.org/abs/2303.08102v1
- Date: Tue, 14 Mar 2023 17:41:31 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-15 13:48:00.589332
- Title: Information-Theoretic Regret Bounds for Bandits with Fixed Expert Advice
- Title(参考訳): 固定専門家アドバイザを用いた帯域情報理論レグレクト境界
- Authors: Khaled Eldowa, Nicol\`o Cesa-Bianchi, Alberto Maria Metelli, Marcello
Restelli
- Abstract要約: 本研究は,専門家が修正され,行動上の既知の分布を把握した場合に,専門家の助言で盗賊の問題を調査するものである。
この設定における後悔は、専門家間の類似度を測定する情報理論量によって制御されていることを示す。
- 参考スコア(独自算出の注目度): 40.32303434592863
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We investigate the problem of bandits with expert advice when the experts are
fixed and known distributions over the actions. Improving on previous analyses,
we show that the regret in this setting is controlled by information-theoretic
quantities that measure the similarity between experts. In some natural special
cases, this allows us to obtain the first regret bound for EXP4 that can get
arbitrarily close to zero if the experts are similar enough. While for a
different algorithm, we provide another bound that describes the similarity
between the experts in terms of the KL-divergence, and we show that this bound
can be smaller than the one of EXP4 in some cases. Additionally, we provide
lower bounds for certain classes of experts showing that the algorithms we
analyzed are nearly optimal in some cases.
- Abstract(参考訳): 我々は,専門家が修正され,行動に関する既知の分布が存在する場合に,専門家のアドバイスにより,バンディットの問題を調査する。
先行分析を改良した結果,後悔は専門家間の類似性を測定する情報理論量によって制御されることがわかった。
いくつかの自然の特殊ケースでは、専門家が十分に類似しているならば、任意に0に近づくことができるEXP4の最初の後悔境界が得られる。
別のアルゴリズムでは、kl-ダイバージェンスの観点から専門家間の類似性を記述する別のバウンドを提供し、ある場合においてこのバウンドが exp4 のバウンドよりも小さいことを示す。
さらに、ある専門家のクラスに対して、分析したアルゴリズムがほぼ最適であることを示す下限を提供する。
関連論文リスト
- Weighting Experts with Inaccurate Judges [31.564788318133264]
審査員のアンサンブルを使って専門家を重み付けすれば、どの審査員よりも優れた重み付けが得られる。
審査員と専門家のエージェントの最適な分割が、どのように分布に依存するかを示す。
論文 参考訳(メタデータ) (2022-11-15T20:47:14Z) - Precise Regret Bounds for Log-loss via a Truncated Bayesian Algorithm [14.834625066344582]
対数損失下での逐次的オンライン回帰(シーケンシャル確率代入)について検討する。
我々は、専門家のクラスで発生する過剰な損失として定義される連続したミニマックスの後悔に対して、厳密で、しばしば一致し、下限と上限を得ることに重点を置いている。
論文 参考訳(メタデータ) (2022-05-07T22:03:00Z) - Second Order Regret Bounds Against Generalized Expert Sequences under
Partial Bandit Feedback [0.0]
本稿では,部分帯域フィードバック設定下でのエキスパートアドバイスの問題について検討し,逐次ミニマックス最適アルゴリズムを作成する。
本アルゴリズムは,従来の帯域幅フィードバックとは対照的に,逆向きに損失を明らかにすることのできる,より一般的な部分的監視設定で動作する。
論文 参考訳(メタデータ) (2022-04-13T22:48:12Z) - Fast rates for prediction with limited expert advice [0.0]
本稿では,情報へのアクセスが制限された有限族における最高の専門家予測に関して,過大な一般化誤差を最小化する問題について検討する。
トレーニングフェーズにおけるTラウンド1ラウンドあたりのエキスパートのアドバイスを1人だけ見ることができれば、最悪の場合の過剰リスクはOmega$(1/$sqrt$T)であり、確率は一定値以下であることが示される。
この設定でこの速度を達成するための新しいアルゴリズムを設計し、与えられた一般化誤差の精度を達成するのに必要な訓練ラウンド数とクエリ数に正確にインスタンス依存のバウンダリを与える。
論文 参考訳(メタデータ) (2021-10-27T14:57:36Z) - Nonstochastic Bandits with Infinitely Many Experts [1.7188280334580197]
無限に多くの専門家と非確率的盗賊の問題を考察する。
有限個の専門家に対して、正しい専門家ランキングの推測を可能にするExp4.Pの変種を提案する。
そして、この変種を無限に多くの専門家に作用するメタアルゴリズムに組み込む。
論文 参考訳(メタデータ) (2021-02-09T22:42:36Z) - Leveraging Expert Consistency to Improve Algorithmic Decision Support [89.01584399789951]
歴史的専門家の意思決定を豊富な情報源として利用することを検討します。
観察されたラベルだけで学習する制限を緩和するために活用できることを示しています。
論文 参考訳(メタデータ) (2021-01-24T05:40:29Z) - Instance-Dependent Complexity of Contextual Bandits and Reinforcement
Learning: A Disagreement-Based Perspective [104.67295710363679]
古典的なマルチアームバンディット問題において、インスタンス依存アルゴリズムは、ベストとセカンドベストのアーム間のギャップで「容易」な問題のパフォーマンスを向上させる。
我々は、インスタンス依存の後悔境界を得るのに十分かつ必要である複雑性尺度のファミリーを導入する。
次に、可能な限りギャップに適応する新しいオラクル効率アルゴリズムを導入し、最悪の場合にはミニマックスレートを得る。
論文 参考訳(メタデータ) (2020-10-07T01:33:06Z) - Relative Deviation Margin Bounds [55.22251993239944]
我々はRademacher複雑性の観点から、分布依存と一般家庭に有効な2種類の学習境界を与える。
有限モーメントの仮定の下で、非有界な損失関数に対する分布依存的一般化境界を導出する。
論文 参考訳(メタデータ) (2020-06-26T12:37:17Z) - Malicious Experts versus the multiplicative weights algorithm in online
prediction [85.62472761361107]
2人の専門家と1人の予測者による予測問題を考える。
専門家の一人が正直で、各ラウンドで確率$mu$で正しい予測をしていると仮定する。
もう一つは悪意のあるもので、各ラウンドで真の結果を知り、予測者の損失を最大化するために予測を行う。
論文 参考訳(メタデータ) (2020-03-18T20:12:08Z) - Prediction with Corrupted Expert Advice [67.67399390910381]
ステップサイズを減らした古典的乗法重みアルゴリズムの変種が、良質な環境において絶え間なく後悔することを証明する。
我々の結果は、しばしば同等のFollow the Regularized Leader(FTRL)とOnline Mirror Descent(OMD)フレームワークの驚くべき相違を明らかにします。
論文 参考訳(メタデータ) (2020-02-24T14:39:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。