論文の概要: Exploration by Optimization with Hybrid Regularizers: Logarithmic Regret
with Adversarial Robustness in Partial Monitoring
- arxiv url: http://arxiv.org/abs/2402.08321v1
- Date: Tue, 13 Feb 2024 09:34:22 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-14 15:52:22.224809
- Title: Exploration by Optimization with Hybrid Regularizers: Logarithmic Regret
with Adversarial Robustness in Partial Monitoring
- Title（参考訳）: ハイブリッド正規化器による最適化による探索:部分モニタリングにおける対数ロバスト性をもつ対数回帰
- Authors: Taira Tsuchiya, Shinji Ito, Junya Honda
- Abstract要約: 敵環境における最適境界を実現するための最適化による探索(ExO)が提案された。
まず,ハイブリッド正規化器を用いたExOの新しいフレームワークと解析手法を構築した。
特に、$O(sum_a neq a* k2 log T / Delta_a)$で、$a*$は最適なアクションであり、$Delta_a$はアクションの亜最適ギャップである。
- 参考スコア（独自算出の注目度）: 46.30750729936261
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Partial monitoring is a generic framework of online decision-making problems
with limited observations. To make decisions from such limited observations, it
is necessary to find an appropriate distribution for exploration. Recently, a
powerful approach for this purpose, exploration by optimization (ExO), was
proposed, which achieves the optimal bounds in adversarial environments with
follow-the-regularized-leader for a wide range of online decision-making
problems. However, a naive application of ExO in stochastic environments
significantly degrades regret bounds. To resolve this problem in locally
observable games, we first establish a novel framework and analysis for ExO
with a hybrid regularizer. This development allows us to significantly improve
the existing regret bounds of best-of-both-worlds (BOBW) algorithms, which
achieves nearly optimal bounds both in stochastic and adversarial environments.
In particular, we derive a stochastic regret bound of $O(\sum_{a \neq a^*} k^2
m^2 \log T / \Delta_a)$, where $k$, $m$, and $T$ are the numbers of actions,
observations and rounds, $a^*$ is an optimal action, and $\Delta_a$ is the
suboptimality gap for action $a$. This bound is roughly $\Theta(k^2 \log T)$
times smaller than existing BOBW bounds. In addition, for globally observable
games, we provide a new BOBW algorithm with the first $O(\log T)$ stochastic
bound.
- Abstract（参考訳）: 部分的監視は、限定的な観察を伴うオンライン意思決定問題の一般的なフレームワークである。
このような限られた観測から決定を下すには、探査に適切な分布を見つける必要がある。
近年,様々なオンライン意思決定問題に対して,フォロー・ザ・レギュラライズ・リーダーを伴う敵環境における最適境界を達成するための,最適化による探索(exploreing by optimization,exo)という強力なアプローチが提案されている。
しかし、確率的環境におけるExOの単純適用は、後悔境界を著しく低下させる。
局所観測可能なゲームにおいてこの問題を解決するために,我々はまず,ハイブリッド正規化器を用いたExOの新しいフレームワークと解析を行う。
この開発により、確率的および対角的環境の両方においてほぼ最適な境界を達成できるBOBWアルゴリズムの既存の後悔境界を大幅に改善することができる。
特に、$o(\sum_{a \neq a^*} k^2 m^2 \log t / \delta_a)$、ここで$k$、$m$、$t$はアクション、観察、ラウンドの数であり、$a^*$は最適なアクションであり、$\delta_a$はアクション$a$の準最適ギャップである。
この境界は、既存のBOBW境界の約$\Theta(k^2 \log T)$倍小さい。
さらに、グローバルな可観測ゲームに対しては、最初の$O(\log T)$確率境界を持つ新しいBOBWアルゴリズムを提供する。
関連論文リスト
- Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Best-of-Both-Worlds Algorithms for Linear Contextual Bandits [11.94312915280916]
両世界のベスト・オブ・ワールドズ・アルゴリズムを$K$武器付き線形文脈包帯に対して検討する。
我々のアルゴリズムは、敵対的体制と敵対的体制の両方において、ほぼ最適の後悔の限界を提供する。
論文 参考訳（メタデータ） (2023-12-24T08:27:30Z) - Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳（メタデータ） (2023-12-13T11:08:25Z) - Best-of-Three-Worlds Linear Bandit Algorithm with Variance-Adaptive
Regret Bounds [27.92755687977196]
本稿では,2つの階層の環境に適応する線形帯域幅アルゴリズムを提案する。
高いレベルでは、提案アルゴリズムは様々な種類の環境に適応する。
提案アルゴリズムは、最適動作に対する累積損失のすべてに依存する、データ依存の後悔境界を有する。
論文 参考訳（メタデータ） (2023-02-24T00:02:24Z) - Adversarially Robust Multi-Armed Bandit Algorithm with
Variance-Dependent Regret Bounds [34.37963000493442]
本稿では,マルチアーム・バンディット(MAB)問題について考察し,両対向的条件下でほぼ最適に機能する,新たなベスト・オブ・ボス・ワールド(BOBW)アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-06-14T12:58:46Z) - Towards Painless Policy Optimization for Constrained MDPs [46.12526917024248]
我々は、無限の地平線における政策最適化、$gamma$-discounted constrained Markov decision process (CMDP)について研究する。
我々の目標は、小さな制約違反で大きな期待された報酬を達成する政策を返却することである。
本稿では,任意のアルゴリズムに対して,報酬の準最適性と制約違反を拘束できる汎用的原始双対フレームワークを提案する。
論文 参考訳（メタデータ） (2022-04-11T15:08:09Z) - Bayesian Optimistic Optimisation with Exponentially Decaying Regret [58.02542541410322]
現在の実用的なBOアルゴリズムは、$mathcalO(fraclogNsqrtN)$から$mathcalO(e-sqrtN)$まで、$N$は評価の数である。
本稿では,boと木に基づく楽観的楽観化の概念を絡み合うことにより,無音環境における後悔を改善できる可能性について検討する。
次数$mathcal O(N-sqrt)で指数的再帰を達成できる最初の実践的手法であるBOOアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-05-10T13:07:44Z) - Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive
Multi-Step Bootstrap [84.66885506098724]
本稿では,アダプティブ・マルチステップ・ブートストラップ (AMB) を用いた表層有限水平マルコフ決定過程 (MDP) のモデルフリーアルゴリズムを提案する。
AMBは,部分最適ギャップの逆の和でのみスケールする,ギャップ依存的後悔境界を達成できることを示す。
また、AMB は $frac|Z_mul|Delta_min$ regret という追加の $frac|Z_mul|Delta_min$ を被っていることも示しています。
論文 参考訳（メタデータ） (2021-02-09T07:46:34Z) - Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits
with Linear Payoff Functions [53.77572276969548]
我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。
一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-20T04:29:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。