論文の概要: Best-of-Both-Worlds Algorithms for Partial Monitoring
- arxiv url: http://arxiv.org/abs/2207.14550v1
- Date: Fri, 29 Jul 2022 08:40:05 GMT
- ステータス: 処理完了
- システム内更新日: 2022-08-01 12:28:01.316455
- Title: Best-of-Both-Worlds Algorithms for Partial Monitoring
- Title（参考訳）: 部分モニタリングのためのBest-of-Both-Worldsアルゴリズム
- Authors: Taira Tsuchiya, Shinji Ito, Junya Honda
- Abstract要約: 非退化したグローバル可観測ゲームでは、レジームの後悔は$O(k3 m2 log(k_Pi T) / Delta_min2)$で制限される。
我々のアルゴリズムは、フィードバックグラフを用いたオンライン学習の分野におけるアルゴリズムにインスパイアされた、フォロー・ザ・レギュラライズド・リーダー・フレームワークに基づいている。
- 参考スコア（独自算出の注目度）: 34.37963000493442
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper considers the partial monitoring problem with $k$-actions and
$d$-outcomes and provides the first best-of-both-worlds algorithms, whose
regrets are bounded poly-logarithmically in the stochastic regime and
near-optimally in the adversarial regime. To be more specific, we show that for
non-degenerate locally observable games, the regret in the stochastic regime is
bounded by $O(k^3 m^2 \log(T) \log(k_{\Pi} T) / \Delta_{\mathrm{\min}})$ and in
the adversarial regime by $O(k^{2/3} m \sqrt{T \log(T) \log k_{\Pi}})$, where
$T$ is the number of rounds, $m$ is the maximum number of distinct observations
per action, $\Delta_{\min}$ is the minimum optimality gap, and $k_{\Pi}$ is the
number of Pareto optimal actions. Moreover, we show that for non-degenerate
globally observable games, the regret in the stochastic regime is bounded by
$O(\max\{c_{\mathcal{G}}^2 / k,\, c_{\mathcal{G}}\} \log(T) \log(k_{\Pi} T) /
\Delta_{\min}^2)$ and in the adversarial regime by $O((\max\{c_{\mathcal{G}}^2
/ k,\, c_{\mathcal{G}}\} \log(T) \log(k_{\Pi} T)))^{1/3} T^{2/3})$, where
$c_{\mathcal{G}}$ is a game-dependent constant. Our algorithms are based on the
follow-the-regularized-leader framework that takes into account the nature of
the partial monitoring problem, inspired by algorithms in the field of online
learning with feedback graphs.
- Abstract（参考訳）: 本稿では,$k$-actions と $d$-outcomes による部分的監視問題を考察し,その後悔が確率的体制と対向的体制においてほぼ最適に多対数に有界である最初のベスト・オブ・バイ・バイザー・ワールドアルゴリズムを提供する。
より具体的に言うと、非退化の局所可観測ゲームの場合、確率的体制における後悔は$O(k^3 m^2 \log(T) \log(k_{\Pi} T) / \Delta_{\mathrm{\min}})$と、$O(k^{2/3} m \sqrt{T \log(T) \log k_{\Pi}})$で有界であり、$T$はラウンド数、$m$はアクションごとに異なる観測の最大値、$\Delta_{\min}$は最小の最適性ギャップ、$k_{\Pi}$はパレートの最適アクションの数である。
さらに、非退化可観測ゲームに対しては、確率的状態における後悔は、$O(\max\{c_{\mathcal{G}}^2 / k,\, c_{\mathcal{G}}\} \log(T) \log(k_{\Pi} T) / \Delta_{\min}^2)$と、$O((\max\{c_{\mathcal{G}}^2 / k,\, c_{\mathcal{G}}\} \log(T) \log(k_{\Pi} T)))^{1/3} T^{2/3})$と有界であることが示される。
我々のアルゴリズムは、フィードバックグラフを用いたオンライン学習の分野におけるアルゴリズムに触発された部分監視問題の性質を考慮した、フォロー・ザ・レギュラライズド・リーダー・フレームワークに基づいている。
関連論文リスト
- Online Newton Method for Bandit Convex Optimisation [28.66596225688161]
ゼロ階帯域幅の最適化のための計算効率の良いアルゴリズムを提案する。
逆条件では、その後悔は少なくとも$d3.5 sqrtn Mathrmpolylog(n, d)$であり、d$が時間的地平線である確率が高いことを証明している。
設定において、バウンダリは$M d2 sqrtn Mathrmpolylog(n, d)$に改善され、[d-1/2, d-1 / 4]$は$Mとなる。
論文 参考訳（メタデータ） (2024-06-10T17:44:11Z) - Batched Stochastic Bandit for Nondegenerate Functions [8.015503209312786]
本稿では,非退化関数に対するバッチ帯域学習問題について検討する。
本稿では,非退化関数に対するバッチバンドイット問題をほぼ最適に解くアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-05-09T12:50:16Z) - Best-of-Both-Worlds Algorithms for Linear Contextual Bandits [11.94312915280916]
両世界のベスト・オブ・ワールドズ・アルゴリズムを$K$武器付き線形文脈包帯に対して検討する。
我々のアルゴリズムは、敵対的体制と敵対的体制の両方において、ほぼ最適の後悔の限界を提供する。
論文 参考訳（メタデータ） (2023-12-24T08:27:30Z) - Dueling Optimization with a Monotone Adversary [35.850072415395395]
凸最適化の一般化である単調逆数を用いたデュエル最適化の問題点について検討する。
目的は、最小値$mathbfx*$の関数$fcolon XをmathbbRdに変換するために、オンラインアルゴリズムを設計することである。
論文 参考訳（メタデータ） (2023-11-18T23:55:59Z) - 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) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - 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) - Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。
最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
論文 参考訳（メタデータ） (2020-03-04T07:36:38Z) - Tight Regret Bounds for Noisy Optimization of a Brownian Motion [118.65407541895851]
本稿では,1次元ブラウン運動のベイズ最適化の問題点について考察する。
Omega(sigmasqrtT cdot log T)$.sigmasqrtT cdot log T)$.sigmasqrtT.sigmasqrtT.sigmasqrtT cdot log T)$.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.
論文 参考訳（メタデータ） (2020-01-25T14:44:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。