論文の概要: The Gittins Index: A Design Principle for Decision-Making Under Uncertainty

• arxiv url: http://arxiv.org/abs/2506.10872v1
• Date: Thu, 12 Jun 2025 16:38:51 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-13 15:37:22.839126
• Title: The Gittins Index: A Design Principle for Decision-Making Under Uncertainty
• Title（参考訳）: Gittins Index: 不確実性の下での意思決定のための設計原則
• Authors: Ziv Scully, Alexander Terenin,
• Abstract要約: Gittinsインデックスは、不確実性に関わるさまざまな意思決定問題を最適に解決するツールである。 このチュートリアルは、Gittinsインデックスが実践的な問題に実効的に適用可能であることを実証するものだ。
• 参考スコア（独自算出の注目度）: 52.07646284204206
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Gittins index is a tool that optimally solves a variety of decision-making problems involving uncertainty, including multi-armed bandit problems, minimizing mean latency in queues, and search problems like the Pandora's box model. However, despite the above examples and later extensions thereof, the space of problems that the Gittins index can solve perfectly optimally is limited, and its definition is rather subtle compared to those of other multi-armed bandit algorithms. As a result, the Gittins index is often regarded as being primarily a concept of theoretical importance, rather than a practical tool for solving decision-making problems. The aim of this tutorial is to demonstrate that the Gittins index can be fruitfully applied to practical problems. We start by giving an example-driven introduction to the Gittins index, then walk through several examples of problems it solves - some optimally, some suboptimally but still with excellent performance. Two practical highlights in the latter category are applying the Gittins index to Bayesian optimization, and applying the Gittins index to minimizing tail latency in queues.
• Abstract（参考訳）: Gittinsインデックスは、マルチアームのバンディット問題、キューの平均レイテンシの最小化、Pandoraのボックスモデルのような検索問題など、不確実性に関わるさまざまな意思決定問題を最適に解決するツールである。 しかし、上記の例やその後の拡張にもかかわらず、Gittinsインデックスが完全に最適に解くことができる問題の空間は制限されており、その定義は他のマルチ武器のバンディットアルゴリズムと比べてかなり微妙である。 結果として、Gittinsインデックスは意思決定問題を解決するための実用的なツールではなく、理論上重要な概念であると見なされることが多い。 このチュートリアルの目的は、Gittinsインデックスが実践的な問題に実効的に適用可能であることを実証することである。 まず、Gittinsインデックスの例駆動による紹介から始め、解決する問題の例をいくつか紹介します。 後者のカテゴリでは、ベイズ最適化にGittinsインデックスを適用し、キューのテールレイテンシを最小限にするためにGittinsインデックスを適用している。

関連論文リスト

• Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget [55.938644481736446]
  本稿では,誤差確率の指数的減衰を保証し,最適な腕識別のための新しいアルゴリズムを提案する。 我々は,複雑性のレベルが異なる様々な問題インスタンスに対する包括的経験的評価を通じて,アルゴリズムの有効性を検証する。
  論文  参考訳（メタデータ） (2025-06-03T02:56:26Z)
• Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
  本稿では,バッチ取得のための新しいグリーディ型サブセット選択アルゴリズムを提案する。 赤蛍光タンパク質に関する実験により,提案手法は1.69倍少ないクエリでベースライン性能を達成できることが判明した。
  論文  参考訳（メタデータ） (2024-06-21T05:57:08Z)
• Tabular and Deep Reinforcement Learning for Gittins Index [3.7209456282942734]
  マルチアームバンディット問題において、Gittinsインデックスポリシーは、マルコフの腕を引っ張ることで得られる期待の総割引報酬を最大化するのに最適であることが知られている。 ほとんどの現実的なシナリオでは、マルコフ状態遷移確率は未知であるため、Gittinsインデックスは計算できない。 次に、得られた報酬を最大限に活用しながら、状態空間を探索してこれらの指標を学習する強化学習(RL)アルゴリズムを利用することができる。
  論文  参考訳（メタデータ） (2024-05-02T10:19:32Z)
• Indexability is Not Enough for Whittle: Improved, Near-Optimal Algorithms for Restless Bandits [30.532795983761314]
  本研究では,複数の行動を伴うレスレス・マルチアーム・バンディット(RMAB)の計画問題について検討する。 まず、Whittleインデックスポリシーは、シンプルで実用的な設定で失敗する可能性があることを示す。 次に,平均場法に基づく代替計画アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-10-31T19:35:15Z)
• Fast Feature Selection with Fairness Constraints [49.142308856826396]
  モデル構築における最適特徴の選択に関する基礎的問題について検討する。 この問題は、greedyアルゴリズムの変種を使用しても、大規模なデータセットで計算的に困難である。 適応クエリモデルは,最近提案された非モジュラー関数に対する直交整合探索のより高速なパラダイムに拡張する。 提案アルゴリズムは、適応型クエリモデルにおいて指数関数的に高速な並列実行を実現する。
  論文  参考訳（メタデータ） (2022-02-28T12:26:47Z)
• Preference learning along multiple criteria: A game-theoretic perspective [97.94912276610002]
  我々は、ブラックウェルの接近性からインスピレーションを得て、フォン・ノイマンの勝者の概念をマルチ基準設定に一般化する。 本フレームワークは,基準間の選好の非線形集約を可能にし,多目的最適化から線形化に基づくアプローチを一般化する。 凸最適化問題の解法として,マルチ基準問題インスタンスのブラックウェルの勝者が計算可能であることを示す。
  論文  参考訳（メタデータ） (2021-05-05T03:23:11Z)
• Be Greedy in Multi-Armed Bandits [22.301793734117805]
  グレディアルゴリズムは、各ラウンドで局所最適選択を行う、シーケンシャルな決定問題の最も単純なものである。 We provide a generic worst-case bound on the regret of the Greedy algorithm。 連続・無限・多武装バンディット問題において,ほぼ最適の最悪の後悔境界を検証できることを証明した。
  論文  参考訳（メタデータ） (2021-01-04T16:47:02Z)
• Corruption-Tolerant Gaussian Process Bandit Optimization [130.60115798580136]
  未知(典型的には非生成)関数を有界ノルムで最適化する問題を考察する。 我々は「高速だが非ローバスト」と「スロー」に基づく高速スローGP-UCBに基づくアルゴリズムを提案する。 ある種の依存関係は、汚職レベルによっては要求できない、と我々は主張する。
  論文  参考訳（メタデータ） (2020-03-04T09:46:58Z)

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

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