論文の概要: Corruption-Robust Contextual Search through Density Updates
- arxiv url: http://arxiv.org/abs/2206.07528v1
- Date: Wed, 15 Jun 2022 13:18:52 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-16 15:13:04.980350
- Title: Corruption-Robust Contextual Search through Density Updates
- Title（参考訳）: 密度更新による汚職ロバストコンテクスト検索
- Authors: Renato Paes Leme, Chara Podimata, and Jon Schneider
- Abstract要約: 逆雑音モデルにおける文脈探索の問題について検討する。
d$を問題の次元とし、T$を時間軸とし、C$をシステム内のノイズの総量とする。
- 参考スコア（独自算出の注目度）: 28.474451077732287
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of contextual search in the adversarial noise model. Let
$d$ be the dimension of the problem, $T$ be the time horizon and $C$ be the
total amount of noise in the system. For the $\eps$-ball loss, we give a tight
regret bound of $O(C + d \log(1/\eps))$ improving over the $O(d^3 \log(1/\eps))
\log^2(T) + C \log(T) \log(1/\eps))$ bound of Krishnamurthy et al (STOC21). For
the symmetric loss, we give an efficient algorithm with regret $O(C+d \log T)$.
Our techniques are a significant departure from prior approaches.
Specifically, we keep track of density functions over the candidate vectors
instead of a knowledge set consisting of the candidate vectors consistent with
the feedback obtained.
- Abstract（参考訳）: 逆雑音モデルにおける文脈探索の問題について検討する。
d$を問題の次元とし、T$を時間軸とし、C$をシステム内のノイズの総量とする。
$\eps$-ball損失に対して、$O(C + d \log(1/\eps))$$O(d^3 \log(1/\eps)) \log^2(T) + C \log(T) \log(1/\eps))$Krishnamurthy et al (STOC21) の厳密な後悔境界を与える。
対称損失に対して、後悔する$O(C+d \log T)$の効率的なアルゴリズムを与える。
私たちの技術は、以前のアプローチから大きく離れています。
具体的には、得られたフィードバックに一致した候補ベクトルからなる知識セットの代わりに、候補ベクトル上の密度関数の追跡を行う。
関連論文リスト
- Batched Stochastic Bandit for Nondegenerate Functions [8.015503209312786]
本稿では,非退化関数に対するバッチ帯域学習問題について検討する。
本稿では,非退化関数に対するバッチバンドイット問題をほぼ最適に解くアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-05-09T12:50:16Z) - Asymptotically Optimal Pure Exploration for Infinite-Armed Bandits [4.811176167998627]
我々は、未知の分布から生じる無限に多くのバンドイットアームを用いて純粋探索を研究する。
私たちのゴールは、平均的な報酬が1-delta$の1つの高品質なアームを、最高の$eta$-fraction of armsの1つとして$varepsilon$内で効率的に選択することにあります。
論文 参考訳（メタデータ） (2023-06-03T04:00:47Z) - 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) - Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
本研究では,有限水平マルコフ決定過程(MDP)によってモデル化されたエピソディック強化学習(RL)問題をバッチ数に制約を加えて検討する。
我々は,$tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot)をほぼ最適に後悔するアルゴリズムを設計し,$(S,A,H,K)$の対数項を$K$で隠蔽する。
技術的貢献は2つある: 1) 探索のためのほぼ最適設計スキーム
論文 参考訳（メタデータ） (2022-10-15T09:22:22Z) - ARCS: Accurate Rotation and Correspondence Search [21.01267270902429]
本論文は,「同時回転・対応探索」と呼ばれる,より汎用的な古いワフバ問題について述べる。
まず最初に、例えば$m,napprox 106$ を 0.1$ 秒で解けるように、$O(mlog m)$ time と $O(m)$ space, iv) を用いる。
論文 参考訳（メタデータ） (2022-03-28T04:42:11Z) - Logarithmic Regret from Sublinear Hints [76.87432703516942]
自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。
また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
論文 参考訳（メタデータ） (2021-11-09T16:50:18Z) - 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) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。