論文の概要: Taking a hint: How to leverage loss predictors in contextual bandits?
- arxiv url: http://arxiv.org/abs/2003.01922v2
- Date: Thu, 15 Oct 2020 17:31:50 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-26 12:25:31.542032
- Title: Taking a hint: How to leverage loss predictors in contextual bandits?
- Title（参考訳）: ヒント: コンテキストバンディットにおける損失予測器の活用方法?
- Authors: Chen-Yu Wei, Haipeng Luo, Alekh Agarwal
- Abstract要約: 我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。
最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
- 参考スコア（独自算出の注目度）: 63.546913998407405
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We initiate the study of learning in contextual bandits with the help of loss
predictors. The main question we address is whether one can improve over the
minimax regret $\mathcal{O}(\sqrt{T})$ for learning over $T$ rounds, when the
total error of the predictor $\mathcal{E} \leq T$ is relatively small. We
provide a complete answer to this question, including upper and lower bounds
for various settings: adversarial versus stochastic environments, known versus
unknown $\mathcal{E}$, and single versus multiple predictors. We show several
surprising results, such as 1) the optimal regret is
$\mathcal{O}(\min\{\sqrt{T}, \sqrt{\mathcal{E}}T^\frac{1}{4}\})$ when
$\mathcal{E}$ is known, a sharp contrast to the standard and better bound
$\mathcal{O}(\sqrt{\mathcal{E}})$ for non-contextual problems (such as
multi-armed bandits); 2) the same bound cannot be achieved if $\mathcal{E}$ is
unknown, but as a remedy, $\mathcal{O}(\sqrt{\mathcal{E}}T^\frac{1}{3})$ is
achievable; 3) with $M$ predictors, a linear dependence on $M$ is necessary,
even if logarithmic dependence is possible for non-contextual problems.
We also develop several novel algorithmic techniques to achieve matching
upper bounds, including 1) a key action remapping technique for optimal regret
with known $\mathcal{E}$, 2) implementing Catoni's robust mean estimator
efficiently via an ERM oracle leading to an efficient algorithm in the
stochastic setting with optimal regret, 3) constructing an underestimator for
$\mathcal{E}$ via estimating the histogram with bins of exponentially
increasing size for the stochastic setting with unknown $\mathcal{E}$, and 4) a
self-referential scheme for learning with multiple predictors, all of which
might be of independent interest.
- Abstract（参考訳）: 我々は,損失予測者の助けを借りて,文脈的バンディットにおける学習の研究を開始する。
主な疑問は、予測子 $\mathcal{E} \leq T$ の総誤差が比較的小さいとき、$T$ 以上のラウンドを学習するために、minimax regret $\mathcal{O}(\sqrt{T})$ よりも改善できるかどうかである。
この質問に対する完全な答えは、様々な設定における上界と下界を含む:敵対確率環境、既知の対未知の$\mathcal{e}$、単一対複数の予測器。
我々はいくつかの驚くべき結果を示す。
1) 最適な後悔は$\mathcal{O}(\min\{\sqrt{T}, \sqrt{\mathcal{E}}T^\frac{1}{4}\})$である。
2)$\mathcal{E}$が未知ならば同じ境界は達成できないが、救済策として$\mathcal{O}(\sqrt{\mathcal{E}}T^\frac{1}{3})$は達成可能である。
3)$m$予測器では,非文脈問題に対して対数依存が可能であっても,$m$に対する線形依存が必要である。
また,上界のマッチングを実現するための新しいアルゴリズム手法もいくつか開発している。
1) 既知の$\mathcal{e}$, を持つ最適後悔のためのキーアクション再マッピング手法
2)ermオラクルによるカトーニのロバスト平均推定器の効率的な実装は、最適後悔を伴う確率的設定において効率的なアルゴリズムをもたらす。
3) 未知の$\mathcal{E}$の確率的設定に対して指数関数的に増加する大きさのビンでヒストグラムを推定することで、$\mathcal{E}$の過小評価器を構築する。
4) 複数の予測者による学習のための自己推論スキーム。
関連論文リスト
- Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - Batched Stochastic Bandit for Nondegenerate Functions [8.015503209312786]
本稿では,非退化関数に対するバッチ帯域学習問題について検討する。
本稿では,非退化関数に対するバッチバンドイット問題をほぼ最適に解くアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-05-09T12:50:16Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - Optimism in Face of a Context: Regret Guarantees for Stochastic
Contextual MDP [46.86114958340962]
我々は,最小到達可能性仮定の下での文脈的MDPに対する後悔のアルゴリズムを提案する。
我々のアプローチは、一般関数近似を用いた文脈的MDPに適用された最初の楽観的アプローチである。
論文 参考訳（メタデータ） (2022-07-22T15:00:15Z) - On Submodular Contextual Bandits [92.45432756301231]
作用が基底集合の部分集合であり、平均報酬が未知の単調部分モジュラ函数によってモデル化されるような文脈的包帯の問題を考える。
Inverse Gap Weighting 戦略により,提案アルゴリズムは推定関数の局所的最適度を効率よくランダム化することを示す。
論文 参考訳（メタデータ） (2021-12-03T21:42:33Z) - Evaluating Probabilistic Inference in Deep Learning: Beyond Marginal
Predictions [37.92747047688873]
一般的に使われる$tau=1$は、多くの関心のある設定で良い決定を下すには不十分であることを示す。
さらに、$tau$が成長するにつれて、$mathbfd_mathrmKLtau$は任意の決定に対する普遍的な保証を回復する。
論文 参考訳（メタデータ） (2021-07-20T01:55:01Z) - Improved Regret Bounds for Online Submodular Maximization [10.089520556398575]
我々は、各ステップ$tin[T]$において、固定凸からアクション$x_t$を選択し、コンパクトなドメインセット$mathcalK$を選択するオンライン最適化問題を考える。
ユーティリティ関数 $f_t(cdot)$ が明らかになり、アルゴリズムはペイオフ $f_t(x_t)$ を受け取る。
論文 参考訳（メタデータ） (2021-06-15T02:05:35Z) - Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。
learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。
我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。
ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文 参考訳（メタデータ） (2021-02-15T08:16:51Z) - Thresholded Lasso Bandit [70.17389393497125]
Thresholded Lasso banditは、報酬関数を定義するベクトルとスパースサポートを推定するアルゴリズムである。
一般には $mathcalO( log d + sqrtT )$ や $mathcalO( log d + sqrtT )$ としてスケールする非漸近的後悔の上界を確立する。
論文 参考訳（メタデータ） (2020-10-22T19:14:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。