Fugu-MT 論文翻訳(概要): A Hoeffding Inequality for Finite State Markov Chains and its Applications to Markovian Bandits

論文の概要: A Hoeffding Inequality for Finite State Markov Chains and its Applications to Markovian Bandits

arxiv url: http://arxiv.org/abs/2001.01199v2
Date: Fri, 10 Jul 2020 16:56:28 GMT
ステータス: 処理完了
システム内更新日: 2023-01-14 07:42:56.353673
Title: A Hoeffding Inequality for Finite State Markov Chains and its Applications to Markovian Bandits
Title（参考訳）: 有限状態マルコフ鎖に対するホッフィング不等式とそのマルコフバンドイットへの応用
Authors: Vrettos Moulos
Abstract要約: 本稿では、部分和 $sum_k=1n f (X_k)$, ここで、mathbbZ_> 0$ は有限状態空間 $S$ 上の既約マルコフ連鎖であり、$f : S to [a, b]$ は実数値関数である。
参考スコア（独自算出の注目度）: 10.66048003460524
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: This paper develops a Hoeffding inequality for the partial sums $\sum_{k=1}^n f (X_k)$, where $\{X_k\}_{k \in \mathbb{Z}_{> 0}}$ is an irreducible Markov chain on a finite state space $S$, and $f : S \to [a, b]$ is a real-valued function. Our bound is simple, general, since it only assumes irreducibility and finiteness of the state space, and powerful. In order to demonstrate its usefulness we provide two applications in multi-armed bandit problems. The first is about identifying an approximately best Markovian arm, while the second is concerned with regret minimization in the context of Markovian bandits.
Abstract（参考訳）: 本稿では、部分和 $\sum_{k=1}^n f (x_k)$ に対するホッフィング不等式を開発し、ここで$\{x_k\}_{k \in \mathbb{z}_{> 0}} は有限状態空間上の既約マルコフ連鎖であり、$f : s \to [a, b]$ は実数値関数である。私たちの境界は一般に単純であり、状態空間の既約性と有限性を前提としており、強力である。その有用性を示すために、多武装バンディット問題に2つの応用を提供する。第一は、ほぼ最良のマルコフの腕を特定すること、第二は、マルコフの盗賊の文脈における後悔の最小化に関するものである。

関連論文リスト

Testing the Feasibility of Linear Programs with Bandit Feedback [53.40256244941895]
我々は,低回帰アルゴリズムと反復対数の漸近法則に基づくテストを開発する。このテストが信頼できることを証明し、信号レベルに適応する'$Gamma,$ of any instance。信頼性テストのサンプルコストに対して、最小限の$(Omegad/Gamma2)$で補う。
論文参考訳（メタデータ） (2024-06-21T20:56:35Z)
Dimension Independent Disentanglers from Unentanglement and Applications [55.86191108738564]
両部非絡み込み入力から次元独立なk-パーティイトディジアンタングル(類似)チャネルを構築する。 NEXP を捉えるためには、$| psi rangle = sqrta | sqrt1-a | psi_+ rangle という形の非負の振幅を持つのに十分であることを示す。
論文参考訳（メタデータ） (2024-02-23T12:22:03Z)
Concentration Phenomenon for Random Dynamical Systems: An Operator Theoretic Approach [10.051309746913512]
本稿では, 所定の観測値に対する濃度現象を定式化する。可観測関数/報酬関数が非有界であるとしても、ある意味では非有界であることが判明した。 for some $q>2$, $|er|_q. 濃度現象におけるエンプレバーシビリティの役割はデミスト化されている。
論文参考訳（メタデータ） (2022-12-07T14:36:46Z)
Double Doubly Robust Thompson Sampling for Generalized Linear Contextual Bandits [8.508198765617198]
一般化線形報酬に$tildeO(sqrtkappa-1 phi T)$ regret over $T$ roundsを提案する。また、確率的マージン条件下では、$O(kappa-1 phi log (NT) log T)$ regret bound for $N$ arms も提供する。
論文参考訳（メタデータ） (2022-09-15T00:20:38Z)
A rapidly mixing Markov chain from any gapped quantum many-body system [2.321323878201932]
我々は、$pi(x)=|langle x|psirangle|2$ からビット文字列 $x$ を考える。我々の主な結果は、逆スペクトルギャップ$H$と関連する連続時間Markov Chainと定常状態$pi$の混合時間との直接リンクを記述する。
論文参考訳（メタデータ） (2022-07-14T16:38:42Z)
Variance-Aware Sparse Linear Bandits [64.70681598741417]
余分な線形包帯に対する最悪のミニマックスは$widetildeThetaleft(sqrtdTright)$である。ノイズがなく、アクションセットが単位球面である良性設定では、ディビジョン・アンド・コンカーを使用して、$widetildemathcal O(1)$ regretを達成することができる。我々は,任意の分散対応線形帯域幅アルゴリズムを分散対応線形帯域幅アルゴリズムに変換する汎用フレームワークを開発した。
論文参考訳（メタデータ） (2022-05-26T15:55:44Z)
Low-Complexity Algorithm for Restless Bandits with Imperfect Observations [1.4542411354617986]
我々は、強化学習と最適化において幅広い応用分野を見出す、レスレス・バンディット問題の一類を考察する。我々は,観測誤差を伴う一般的なレスト・バンディット・モデルに容易に適用可能な,高い性能を実現する低複雑性アルゴリズムを開発した。
論文参考訳（メタデータ） (2021-08-09T05:01:19Z)
Restless-UCB, an Efficient and Low-complexity Algorithm for Online Restless Bandits [61.490254407420906]
我々は、各腕の状態がマルコフ連鎖に従って進化するオンラインレス・バンディット問題について研究する。本研究では,探索研究の枠組みに従う学習方針であるReestless-UCBを提案する。
論文参考訳（メタデータ） (2020-11-05T05:16:04Z)
Thresholded Lasso Bandit [70.17389393497125]
Thresholded Lasso banditは、報酬関数を定義するベクトルとスパースサポートを推定するアルゴリズムである。一般には $mathcalO( log d + sqrtT )$ や $mathcalO( log d + sqrtT )$ としてスケールする非漸近的後悔の上界を確立する。
論文参考訳（メタデータ） (2020-10-22T19:14:37Z)
Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals [49.60752558064027]
ガウス境界の下では、半空間とReLUを不可知的に学習する基本的な問題について検討する。我々の下限は、これらのタスクの現在の上限が本質的に最良のものであるという強い証拠を与える。
論文参考訳（メタデータ） (2020-06-29T17:10:10Z)
Nearly Optimal Regret for Stochastic Linear Bandits with Heavy-Tailed Payoffs [35.988644745703645]
我々は、リニアバンディットをヘビーテールのペイオフで分析し、そこではペイオフは1+epsilon$のモーメントしか持たない。本稿では,$widetildeO(dfrac12Tfrac11+epsilon)$のサブ線形後悔境界を満足する2つの新しいアルゴリズムを提案する。
論文参考訳（メタデータ） (2020-04-28T13:01:38Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。