論文の概要: Tabular and Deep Reinforcement Learning for Gittins Index

• arxiv url: http://arxiv.org/abs/2405.01157v1
• Date: Thu, 2 May 2024 10:19:32 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-03 17:04:04.910173
• Title: Tabular and Deep Reinforcement Learning for Gittins Index
• Title（参考訳）: Gittins Indexのためのタブラリとディープ強化学習
• Authors: Harshit Dhankar, Kshitij Mishra, Tejas Bodas,
• Abstract要約: マルチアームバンディット問題の領域では、ギッティンス指数ポリシーはマルコフの腕を引いて得られる期待の総割引報酬を最大化するのに最適であることが知られている。 しかし、ほとんどの現実的なシナリオでは、マルコフ状態遷移確率は未知であり、したがってGittinsインデックスは計算できない。 次に、得られた報酬を最大限に活用しながら、状態空間を探索してこれらの指標を学習する強化学習(RL)アルゴリズムを利用することができる。
• 参考スコア（独自算出の注目度）: 3.7209456282942734
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In the realm of multi-arm bandit problems, the Gittins index policy is known to be optimal in maximizing the expected total discounted reward obtained from pulling the Markovian arms. In most realistic scenarios however, the Markovian state transition probabilities are unknown and therefore the Gittins indices cannot be computed. One can then resort to reinforcement learning (RL) algorithms that explore the state space to learn these indices while exploiting to maximize the reward collected. In this work, we propose tabular (QGI) and Deep RL (DGN) algorithms for learning the Gittins index that are based on the retirement formulation for the multi-arm bandit problem. When compared with existing RL algorithms that learn the Gittins index, our algorithms have a lower run time, require less storage space (small Q-table size in QGI and smaller replay buffer in DGN), and illustrate better empirical convergence to the Gittins index. This makes our algorithm well suited for problems with large state spaces and is a viable alternative to existing methods. As a key application, we demonstrate the use of our algorithms in minimizing the mean flowtime in a job scheduling problem when jobs are available in batches and have an unknown service time distribution. \
• Abstract（参考訳）: マルチアームバンディット問題の領域では、ギッティンス指数ポリシーはマルコフの腕を引いて得られる期待の総割引報酬を最大化するのに最適であることが知られている。 しかし、ほとんどの現実的なシナリオでは、マルコフ状態遷移確率は未知であり、そのためギッティンスの指数は計算できない。 次に、得られた報酬を最大限に活用しながら、状態空間を探索してこれらの指標を学習する強化学習(RL)アルゴリズムを利用することができる。 本研究では,マルチアームバンディット問題の定式化に基づくGittinsインデックスを学習するための表式(QGI)とディープRL(DGN)アルゴリズムを提案する。 Gittinsインデックスを学習する既存のRLアルゴリズムと比較して、当社のアルゴリズムは実行時間が短く、ストレージスペースが小さく(QGIではQテーブルサイズが小さく、DGNではリプレイバッファが小さい)、Gittinsインデックスへの経験的収束性が向上している。 これにより、我々のアルゴリズムは大きな状態空間の問題によく適合し、既存の手法の代替となる。 重要なアプリケーションとして、ジョブがバッチで利用可能で、未知のサービス時間分布を持つ場合、ジョブスケジューリング問題における平均フロータイムを最小化するアルゴリズムの使用を実証する。 名

関連論文リスト

• RAGLAB: A Modular and Research-Oriented Unified Framework for Retrieval-Augmented Generation [54.707460684650584]
  大きな言語モデル(LLM)は対話、推論、知識保持における人間レベルの能力を示す。 現在の研究は、LLMに外部知識を組み込むことによって、このボトルネックに対処している。 RAGLABはモジュール的で研究指向のオープンソースライブラリで、6つの既存のアルゴリズムを再現し、RAGアルゴリズムを調査するための包括的なエコシステムを提供する。
  論文  参考訳（メタデータ） (2024-08-21T07:20:48Z)
• GINO-Q: Learning an Asymptotically Optimal Index Policy for Restless Multi-armed Bandits [16.054685587034836]
  GINO-Qは、レスレスマルチアームバンディット(RMAB)の最適指標ポリシーを学習するために設計された3段階近似アルゴリズムである。 GINO-QはRMABをインデックス化する必要がなく、柔軟性と適用性を高めている。 実験結果から, GINO-Q は非接種可能なRMABに対しても, ほぼ最適に学習できることが示唆された。
  論文  参考訳（メタデータ） (2024-08-19T10:50:45Z)
• Towards Principled, Practical Policy Gradient for Bandits and Tabular MDPs [9.58750210024265]
  バンディットとマルコフ決定過程(MDP)に対する(確率的)ソフトマックスポリシー勾配(PG)法について検討する。 提案アルゴリズムは,技術結果と類似した理論的保証を提供するが,オラクルのような量の知識は必要としないことを示す。 マルチアームバンディット設定の場合,提案手法は明示的な探索や報奨ギャップの知識,報奨分布,ノイズを必要としない理論的なPGアルゴリズムを実現する。
  論文  参考訳（メタデータ） (2024-05-21T18:12:39Z)
• GBM-based Bregman Proximal Algorithms for Constrained Learning [3.667453772837954]
  我々はBregman近位アルゴリズムのフレームワーク内で制約付き学習タスクにGBMを適用する。 本稿では,学習対象関数が凸である場合に,大域的最適性を保証する新しいブレグマン法を提案する。 本稿では,Bregmanアルゴリズムフレームワークの有効性を示すための実験的な証拠を提供する。
  論文  参考訳（メタデータ） (2023-08-21T14:56:51Z)
• Interpretable Option Discovery using Deep Q-Learning and Variational Autoencoders [9.432068833600884]
  DVQNアルゴリズムは、オプションベースの強化学習における開始条件と終了条件を特定するための有望なアプローチである。 実験により、DVQNアルゴリズムは自動開始と終了で、Rainbowに匹敵する性能を示した。
  論文  参考訳（メタデータ） (2022-10-03T21:08:39Z)
• A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
  ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。 このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。 我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-03-28T21:34:16Z)
• Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
  オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。 SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。 本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。 ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
  論文  参考訳（メタデータ） (2021-09-13T18:10:52Z)
• Community detection using fast low-cardinality semidefinite programming [94.4878715085334]
  局所的な更新を一般化し、ライデン-k-カットから導かれる半定緩和を最大化する、新しい低カルチナリティアルゴリズムを提案する。 提案アルゴリズムはスケーラビリティが高く,最先端のアルゴリズムより優れ,実時間では性能が向上し,追加コストがほとんどない。
  論文  参考訳（メタデータ） (2020-12-04T15:46:30Z)
• Resource Allocation in Multi-armed Bandit Exploration: Overcoming Sublinear Scaling with Adaptive Parallelism [107.48538091418412]
  腕の引っ張りに様々な量の資源を割り当てることができる分割可能な資源にアクセス可能な場合,マルチアームの帯状地における探索について検討する。 特に、分散コンピューティングリソースの割り当てに重点を置いており、プル毎により多くのリソースを割り当てることで、結果をより早く得ることができます。
  論文  参考訳（メタデータ） (2020-10-31T18:19:29Z)
• Fast Distributed Bandits for Online Recommendation Systems [22.447455071649852]
  コンテキスト帯域幅アルゴリズムは、コンテンツの人気が急速に変化するレコメンデーションシステムで一般的に使用される。 近年,ユーザ間のクラスタリングやソーシャル構造を学習するリコメンデーションアルゴリズムは,高いレコメンデーション精度を示した。 最先端の分散バンディットアルゴリズム(DCCB)は、分散ワーカー間で情報を共有するためにピアツーピアのネットワークに依存している。 本稿では,DistCLUBと呼ばれる分散帯域幅に基づく新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-07-16T01:18:08Z)
• Model Selection in Contextual Stochastic Bandit Problems [51.94632035240787]
  基本アルゴリズムを選択できるメタアルゴリズムを開発した。 基本アルゴリズムの1つが$O(sqrtT)$後悔している場合でも、一般的には$Omega(sqrtT)$後悔よりも良いものを得ることはできません。
  論文  参考訳（メタデータ） (2020-03-03T18:46:34Z)

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

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