論文の概要: Learning-Augmented Algorithms for MTS with Bandit Access to Multiple Predictors

• arxiv url: http://arxiv.org/abs/2506.05479v1
• Date: Thu, 05 Jun 2025 18:00:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-09 17:28:43.183584
• Title: Learning-Augmented Algorithms for MTS with Bandit Access to Multiple Predictors
• Title（参考訳）: 複数の予測器への帯域アクセスを有するMTSのための学習強化アルゴリズム
• Authors: Matei Gabriel Coşa, Marek Eliáš,
• Abstract要約: 我々は、$O(text2/3)$の後悔をいかに達成するかを示し、Dekel et al の構成に基づいて、厳密な下限を証明する。 これは、メモリ境界の敵に対する学習に関連している。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the following problem: We are given $\ell$ heuristics for Metrical Task Systems (MTS), where each might be tailored to a different type of input instances. While processing an input instance received online, we are allowed to query the action of only one of the heuristics at each time step. Our goal is to achieve performance comparable to the best of the given heuristics. The main difficulty of our setting comes from the fact that the cost paid by a heuristic at time $t$ cannot be estimated unless the same heuristic was also queried at time $t-1$. This is related to Bandit Learning against memory bounded adversaries (Arora et al., 2012). We show how to achieve regret of $O(\text{OPT}^{2/3})$ and prove a tight lower bound based on the construction of Dekel et al. (2013).
• Abstract（参考訳）: 我々は、Metrical Task Systems (MTS)に対して$$\ell$ Heuristicsを与えられ、それぞれが異なるタイプの入力インスタンスに調整される可能性がある。 オンラインで受信した入力インスタンスを処理している間、各ステップで1つのヒューリスティックのアクションのみを問い合わせることができます。 私たちの目標は、与えられたヒューリスティックスのベストに匹敵するパフォーマンスを達成することです。 我々の設定の主な難しさは、時価$t$のヒューリスティックによって支払われるコストが、時価$t-1$で同じヒューリスティックが待ち受けない限り、推定できないという事実にある。 これは、メモリ境界敵に対するBandit Learningに関連している(Arora et al , 2012)。 我々は、$O(\text{OPT}^{2/3})$の後悔をいかに達成するかを示し、Dekel et al (2013) の構成に基づいて、厳密な下界を証明する。

関連論文リスト

• A New Benchmark for Online Learning with Budget-Balancing Constraints [14.818946657685267]
  本稿では,オートバイディングなどの実世界の応用と,その基礎となる数学的構造を比較対象とする新しいベンチマークを提案する。 サブリニアな消費パターンが$o(T2)$以内である戦略に対して,サブリニアな後悔は達成可能であることを示す。
  論文  参考訳（メタデータ） (2025-03-19T00:14:20Z)
• Efficient Reinforcement Learning in Probabilistic Reward Machines [15.645062155050732]
  本稿では,PRM(Probabilistic Reward Machines)のアルゴリズムを設計し,$widetildeO(sqrtHOAT)の償却を達成した。 また,非マルコフ報酬に対する新たなシミュレーション補題を提案し,非マルコフ報酬に対する報酬のない探索を可能にする。
  論文  参考訳（メタデータ） (2024-08-19T19:51:53Z)
• Provably Efficient High-Dimensional Bandit Learning with Batched Feedbacks [93.00280593719513]
  本稿では,オンラインインタラクションのT$ステップをバッチに分割したバッチフィードバックによる高次元マルチアームコンテキストバンドレットについて検討する。 具体的には、各バッチは以前のバッチに依存するポリシーに従ってデータを収集し、その報酬はバッチの最後にのみ明らかにする。 我々のアルゴリズムは,$mathcalO( log T)$ バッチで完全に逐次的に設定されたものに匹敵する後悔の限界を達成している。
  論文  参考訳（メタデータ） (2023-11-22T06:06:54Z)
• Adversarial Online Multi-Task Reinforcement Learning [12.421997449847153]
  対戦型オンラインマルチタスク強化学習環境について考察する。 K$の各エピソードにおいて、学習者は未知のタスクをM$未知有限ホライゾン MDP モデルの有限集合から与えられる。 学習者の目的は,各課題に対する最適方針に関して,その後悔を一般化することである。
  論文  参考訳（メタデータ） (2023-01-11T02:18:26Z)
• Tractable Optimality in Episodic Latent MABs [75.17357040707347]
  我々は、エージェントが時間ステップ$H$のエピソードのために環境と対話する、M$遅延コンテキストを持つマルチアームバンディット問題を考える。 エピソードの長さによっては、学習者は遅れた文脈を正確に見積もることができないかもしれない。 我々は、$O(textttpoly(A) + textttpoly(M,H)min(M,H))$インタラクションを用いて、ほぼ最適なポリシーを確実に学習する手順を設計する。
  論文  参考訳（メタデータ） (2022-10-05T22:53:46Z)
• Nearly Minimax Algorithms for Linear Bandits with Shared Representation [86.79657561369397]
  我々は、次元が$d$で、それぞれ$T$のラウンドで$M$リニアバンディットをプレイする設定を考え、これらの$M$リニアバンディットタスクは共通の$k(ll d)$次元リニア表現を共有する。 我々は$widetildeOleft(dsqrtkMT + kMsqrtTright)$ regret boundsを達成する新しいアルゴリズムを考案した。
  論文  参考訳（メタデータ） (2022-03-29T15:27:13Z)
• No Regrets for Learning the Prior in Bandits [30.478188057004175]
  $tt AdaTS$は、バンディットタスクに順次適応するトンプソンサンプリングアルゴリズムである。 $tt AdaTS$は、バンドイト問題のいくつかのクラスで効率的に実装できる完全ベイズアルゴリズムである。
  論文  参考訳（メタデータ） (2021-07-13T15:51:32Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)
• Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transition [38.28925339231888]
  我々は,世界最良保証付きの最初のアルゴリズムを開発した。 損失が逆ならば、$mathcalO(log T)$ regretを達成します。 より一般的には、中間設定で $tildemathcalO(sqrtC)$ regret を達成する。
  論文  参考訳（メタデータ） (2020-06-10T01:59:34Z)
• Improved Sleeping Bandits with Stochastic Actions Sets and Adversarial Rewards [59.559028338399855]
  我々は,行動セットと敵意の報酬を伴って睡眠中の盗賊の問題を考察する。 本稿では,EXP3にインスパイアされた新しい計算効率のよいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-04-14T00:41:26Z)

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

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