論文の概要: Learning in Markovian bandits with non-observable states and constrained decision epochs

• arxiv url: http://arxiv.org/abs/2606.27448v1
• Date: Thu, 25 Jun 2026 18:18:15 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-29 18:24:25.285339
• Title: Learning in Markovian bandits with non-observable states and constrained decision epochs
• Title（参考訳）: 非可観測状態と制約付き決定エポックを持つマルコフ帯域での学習
• Authors: Thomas Hira, Victor Boone, Urtzi Ayesta, Ina Maria Verloop,
• Abstract要約: 我々は,マルコフの包帯が非可観測状態であり,おそらくは制限された決定のエポックを伴って,後悔の問題を研究した。 バンドイットの根底にある知識がなければ、腕を切り替えるアルゴリズムの後悔は、すべてのバンドイットに対して超論理的にスケールすることが滅多にないことを示す。 マルコフ帯域に関する事前知識が、その腕のバイアス関数に束縛された形で与えられると、UTB-NOMの適切なインスタンス化は、$O(log(T))$ regretとなる。
• 参考スコア（独自算出の注目度）: 4.96981595868944
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper studies the problem of regret minimization in Markovian bandits with \emph{non-observable states} and possibly \emph{constrained} decision epochs. The focus is restricted to a ``pure'' regret benchmark, that compares the performance of the learning algorithm to the best \emph{pure policy} which -- akin to optimal policies of stochastic bandits -- picks the optimal arm from start to finish without ever switching. We introduce a generalization of rested Markovian bandits, \emph{self-degrading Markovian bandits}, for which pure policies are always asymptotically optimal.We show that without prior knowledge on the underlying bandit, the regret of algorithms that switch arms rarely necessarily scales super-logarithmically for every bandit, i.e., as $ω(\log(T))$, where $T$ is the learning horizon. Despite the unreachability of the logarithmic regime, we design UCB-NOM, an optimistic algorithm inspired by UCB, of which the regret is nearly logarithmic. Lastly, we show that given prior knowledge on the Markovian bandit in the form of a bound on the bias functions of its arm, a proper instantiation of UCB-NOM achieves $O(\log(T))$ regret. We further show that this prior knowledge allows for a $O(\sqrt{T \log(T)})$ worst-case regret bound for UCB-NOM. Notably, our regret bounds do not depend on the number of states of the underlying Markov chains. Our findings suggest that the non-observability of states is a mild inconvenience in self-degrading Markovian bandits.
• Abstract（参考訳）: 本稿では,Markovian bandits with \emph{non-observable states} およびおそらく \emph{constrained} decision epochs における後悔の最小化問題について検討する。 このベンチマークは、学習アルゴリズムのパフォーマンスを最高の 'emph{pure policy} と比較するものであり、これは確率的バンディットの最適ポリシーに似たもので、切り替えることなく開始から終了までの最適なアームを選択する。 我々は、純粋ポリシーが常に漸近的に最適である、安楽死的マルコフ的バンディットの一般化を導入し、根底にあるバンディットについて事前の知識がなければ、腕を切り替えるアルゴリズムの後悔は、必ずしもすべてのバンディットに対して超論理的にスケールすることは滅多になく、すなわち$ω(\log(T))$であることを示す。 UCB-NOMという楽観的なアルゴリズムを設計するが、このアルゴリズムはUCBにインスパイアされたものであり、その後悔はほとんど対数的である。 最後に、マルコフ帯域に関する事前の知識が、その腕のバイアス関数に束縛された形で与えられると、UCB-NOMの適切なインスタンス化は、$O(\log(T))$ regretとなることを示す。 さらに、この事前知識が UCB-NOM に対して$O(\sqrt{T \log(T)})$最悪の後悔を許すことを示す。 特に、我々の後悔の限界は、基礎となるマルコフ連鎖の状態の数に依存しない。 その結果, 自己劣化型マルコフバンドでは, 状態の非可観測性は軽度不便であることが示唆された。

関連論文リスト

• Near-Optimal Regret for KL-Regularized Multi-Armed Bandits [54.77408659142336]
  KL正規化目標に対するオンライン学習の統計的効率について検討する。 我々は、MABsのKL正規化後悔が$$非依存であることを示し、$tilde(sqrtKT)$とスケールする。
  論文  参考訳（メタデータ） (2026-03-02T18:17:33Z)
• Complete Policy Regret Bounds for Tallying Bandits [51.039677652803675]
  政策後悔は、適応的な敵に対してオンライン学習アルゴリズムのパフォーマンスを測定するという、よく確立された概念である。 我々は,不完全な政策後悔を効果的に最小化できる敵の制限について検討する。 我々は、$tildemathcalO(mKsqrtT)$の完全なポリシーを後悔するアルゴリズムを提供し、$tildemathcalO$表記は対数要素だけを隠す。
  論文  参考訳（メタデータ） (2022-04-24T03:10:27Z)
• The Best of Both Worlds: Reinforcement Learning with Logarithmic Regret and Policy Switches [84.54669549718075]
  漸進的強化学習(RL)における後悔の最小化問題について検討する。 一般関数クラスと一般モデルクラスで学ぶことに集中する。 対数的後悔境界は$O(log T)$スイッチングコストのアルゴリズムによって実現可能であることを示す。
  論文  参考訳（メタデータ） (2022-03-03T02:55:55Z)
• 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)
• Bandit algorithms: Letting go of logarithmic regret for statistical robustness [0.0]
  我々は,多武器の盗賊設定における後悔について研究し,アルゴリズムによる後悔と統計的堅牢性の間に基本的なトレードオフを確立する。 対数的後悔を伴う帯域学習アルゴリズムは常に矛盾しており、一貫した学習アルゴリズムは常に超対数的後悔に苦しむことを示す。
  論文  参考訳（メタデータ） (2020-06-22T07:18:47Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)
• Contextual Blocking Bandits [35.235375147227124]
  我々は,多腕バンディット問題の新たな変種について検討し,各ステップごとに,腕の平均報酬を決定する独立したサンプルコンテキストをプレイヤーが観察する。 アームを再生することで(すべてのコンテキストにわたって)将来の時間ステップの固定および既知の回数をブロックする。 我々は、$mathcalO(log T)$-regret w.r.t.$alpha$regret戦略を$Tタイムステップで保証し、$Omega(log(T)$low boundと一致する UCB ベースのフル情報アルゴリズムの変種を提案する。
  論文  参考訳（メタデータ） (2020-03-06T20:34:42Z)
• Improved Optimistic Algorithms for Logistic Bandits [16.140301473601454]
  そこで本稿では,報酬関数の非線形性について,より詳細な検証に基づく新しい楽観的アルゴリズムを提案する。 我々は、$tildemathcalO(sqrtT)$ regretを楽しんでおり、$kappa$に依存しないが、第2の順序の項には依存しないことを示す。
  論文  参考訳（メタデータ） (2020-02-18T12:52:32Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。