論文の概要: Understanding the Role of Feedback in Online Learning with Switching
Costs
- arxiv url: http://arxiv.org/abs/2306.09588v1
- Date: Fri, 16 Jun 2023 02:27:41 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-19 15:17:43.275590
- Title: Understanding the Role of Feedback in Online Learning with Switching
Costs
- Title（参考訳）: 切り替えコストによるオンライン学習におけるフィードバックの役割の理解
- Authors: Duo Cheng, Xingyu Zhou, Bo Ji
- Abstract要約: スイッチングコストによるオンライン学習におけるフィードバックの役割について検討する。
フィードバックの量とタイプが一般的に後悔にどのように影響するかは、ほとんど分かっていない。
- 参考スコア（独自算出の注目度）: 13.630306305322096
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we study the role of feedback in online learning with
switching costs. It has been shown that the minimax regret is
$\widetilde{\Theta}(T^{2/3})$ under bandit feedback and improves to
$\widetilde{\Theta}(\sqrt{T})$ under full-information feedback, where $T$ is
the length of the time horizon. However, it remains largely unknown how the
amount and type of feedback generally impact regret. To this end, we first
consider the setting of bandit learning with extra observations; that is, in
addition to the typical bandit feedback, the learner can freely make a total of
$B_{\mathrm{ex}}$ extra observations. We fully characterize the minimax regret
in this setting, which exhibits an interesting phase-transition phenomenon:
when $B_{\mathrm{ex}} = O(T^{2/3})$, the regret remains
$\widetilde{\Theta}(T^{2/3})$, but when $B_{\mathrm{ex}} = \Omega(T^{2/3})$, it
becomes $\widetilde{\Theta}(T/\sqrt{B_{\mathrm{ex}}})$, which improves as the
budget $B_{\mathrm{ex}}$ increases. To design algorithms that can achieve the
minimax regret, it is instructive to consider a more general setting where the
learner has a budget of $B$ total observations. We fully characterize the
minimax regret in this setting as well and show that it is
$\widetilde{\Theta}(T/\sqrt{B})$, which scales smoothly with the total budget
$B$. Furthermore, we propose a generic algorithmic framework, which enables us
to design different learning algorithms that can achieve matching upper bounds
for both settings based on the amount and type of feedback. One interesting
finding is that while bandit feedback can still guarantee optimal regret when
the budget is relatively limited, it no longer suffices to achieve optimal
regret when the budget is relatively large.
- Abstract（参考訳）: 本稿では,スイッチングコストを伴うオンライン学習におけるフィードバックの役割について検討する。
ミニマックスの後悔は、バンディットフィードバックの下で$\widetilde{\theta}(t^{2/3})$であり、全情報フィードバックの下で$\widetilde{\theta}(\sqrt{t})$に改善され、そこで$t$は時間軸の長さである。
しかし、フィードバックの量や種類が一般的に後悔にどのように影響するかはほとんど分かっていない。
この目的のために、我々はまず、余分な観察を伴うバンディット学習の設定を考える。つまり、典型的なバンディットフィードバックに加えて、学習者は合計で$b_{\mathrm{ex}}$余分な観察を自由に行うことができる。
B_{\mathrm{ex}} = O(T^{2/3})$, regret が $\widetilde{\Theta}(T^{2/3})$, しかし、$B_{\mathrm{ex}} = \Omega(T^{2/3})$ が $\widetilde{\Theta}(T/\sqrt{B_{\mathrm{ex}}})$ となると、予算として $B_{\mathrm{ex}}$ が増加する。
最小限の後悔を達成できるアルゴリズムを設計するには、学習者が総観測費$B$の予算を持つより一般的な設定を考える必要がある。
この設定で、minimaxの後悔も完全に特徴づけており、それは$\widetilde{\Theta}(T/\sqrt{B})$であり、総予算$B$で滑らかにスケールすることを示している。
さらに,フィードバックの量や種類に応じて両者の上限を一致させることが可能な,異なる学習アルゴリズムを設計できる汎用的なアルゴリズムフレームワークを提案する。
興味深い発見の1つは、バンディットのフィードバックは予算が比較的限られている場合でも最適な後悔を保証できるが、予算が比較的大きい場合に最適な後悔を達成するにはもはや十分ではないということである。
関連論文リスト
- How Does Variance Shape the Regret in Contextual Bandits? [59.8472760881411]
一般関数近似を用いた文脈的包帯について考察する。
共振器次元 $d_textelu$-$play が分散依存境界において重要な役割を果たすことを示す。
論文 参考訳（メタデータ） (2024-10-16T16:20:07Z) - Adversarial Combinatorial Bandits with Switching Costs [55.2480439325792]
本稿では,各ラウンドで選択したアームのスイッチに対して,切替コストが$lambda$の逆帯域問題について検討する。
ミニマックスの後悔とそれにアプローチするための設計アルゴリズムの限界を低くする。
論文 参考訳（メタデータ） (2024-04-02T12:15:37Z) - Improved Regret for Bandit Convex Optimization with Delayed Feedback [50.46856739179311]
遅延フィードバックを伴うバンド凸最適化(BCO)。
我々は,新しいアルゴリズムを開発し,一般にO(sqrtnT3/4+sqrtdT)$の後悔境界を満足していることを証明する。
提案アルゴリズムは,強い凸関数に対して$O((nT)2/3log/3T+dlog T)$に制限された後悔を改善することができることを示す。
論文 参考訳（メタデータ） (2024-02-14T13:08:26Z) - Minimax Optimal Submodular Optimization with Bandit Feedback [13.805872311596739]
単調な部分モジュラー集合関数 $f: 2[n] rightarrow [0,1]$ をバンドイットフィードバックの下で最大化する。
具体的には、$f$は学習者には知られていないが、各時点で$t=1,dots,T$は、$|S_t| leq k$でセットの$S_tサブセット[n]$を選択し、$eta_t$が平均ゼロのサブガウスノイズである場合に、$f(S_t) + eta_t$を受け取る。
論文 参考訳（メタデータ） (2023-10-27T20:19:03Z) - Online Learning with Feedback Graphs: The True Shape of Regret [82.00098840619847]
ミニマックスの後悔は任意のグラフと時間的地平線に対して$R*$に比例することを示す。
複雑な探索戦略を導入し、最小限の最小後悔境界を達成する主アルゴリズムを定義する。
論文 参考訳（メタデータ） (2023-06-05T15:35:00Z) - Generalized Bandit Regret Minimizer Framework in Imperfect Information
Extensive-Form Game [9.933208900617174]
我々は,IIEGのダイナミクスを知らない対話型バンディットフィードバック設定の問題点を考察する。
NEを学習するには、後悔最小化器は、全フィードバック損失勾配$ellt$ by $v(zt)$を推定し、後悔を最小化する。
モデルフリーであり、$O(sqrtX B/T+sqrtY C/T)$から$O()$までの最良の収束率を大幅に向上させる。
論文 参考訳（メタデータ） (2022-03-11T13:45:42Z) - An Experimental Design Approach for Regret Minimization in Logistic
Bandits [26.674062544226636]
ロジスティックな盗賊の最大の課題は、潜在的に大きな問題に依存する定数$kappa$への依存を減らすことである。
そこで本研究では,新しいウォームアップサンプリングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-02-04T21:56:40Z) - Bandit Phase Retrieval [45.12888201134656]
この問題におけるminimax累積後悔は$smashtilde Theta(d sqrtn)$であることを証明する。
また、minimax の単純な後悔は $smashtilde Theta(d / sqrtn)$ であり、これは適応アルゴリズムによってのみ達成可能であることを示す。
論文 参考訳（メタデータ） (2021-06-03T08:04:33Z) - Adversarial Dueling Bandits [85.14061196945599]
本稿では,反逆デュエルバンドにおける後悔の問題を紹介する。
学習者は、繰り返し一対のアイテムを選択し、このペアに対する相対的な二項利得フィードバックのみを観察しなければならない。
我々の主な成果は、EmphBorda-winnerの1組の$K$アイテムと比較して、T$ラウンド後悔するアルゴリズムです。
論文 参考訳（メタデータ） (2020-10-27T19:09:08Z) - Impact of Representation Learning in Linear Bandits [83.17684841392754]
本研究では,表現学習が帯域幅問題の効率性を向上させる方法について検討する。
我々は,$widetildeO(TsqrtkN + sqrtdkNT)$ regretを達成する新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-10-13T16:35:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。