論文の概要: A Classical Search Game in Discrete Locations

• arxiv url: http://arxiv.org/abs/2103.09310v1
• Date: Mon, 8 Mar 2021 15:16:24 GMT
• ステータス: 処理完了
• システム内更新日: 2021-04-05 00:58:47.443752
• Title: A Classical Search Game in Discrete Locations
• Title（参考訳）: 離散的な位置を探索する古典的検索ゲーム
• Authors: Jake Clarkson, Kyle Y. Lin, Kevin D. Glazebrook
• Abstract要約: 隠れ家と捜索者の間の2人のゼロサムサーチゲームを考える。 ロケーション $i$ での検索は、$t_i$ の時間単位を取得し、隠れている場合は -- 確率 $q_i$ を$i=1,ldots,n$ と独立に検出する。 各プレイヤーに最適な戦略が存在することを証明します。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Consider a two-person zero-sum search game between a hider and a searcher. The hider hides among $n$ discrete locations, and the searcher successively visits individual locations until finding the hider. Known to both players, a search at location $i$ takes $t_i$ time units and detects the hider -- if hidden there -- independently with probability $q_i$, for $i=1,\ldots,n$. The hider aims to maximize the expected time until detection, while the searcher aims to minimize it. We prove the existence of an optimal strategy for each player. In particular, the hider's optimal mixed strategy hides in each location with a nonzero probability, and the searcher's optimal mixed strategy can be constructed with up to $n$ simple search sequences. We develop an algorithm to compute an optimal strategy for each player, and compare the optimal hiding strategy with the simple hiding strategy which gives the searcher no location preference at the beginning of the search.
• Abstract（参考訳）: 隠れ家と捜索者の間の2人のゼロサム検索ゲームを考える。 シーカーは$n$の個別の場所の中に隠れ、サーバーはシーカーを見つけるまで個別の場所を訪れる。 どちらのプレイヤーにも知られているように、ロケーション$i$での検索は、時間単位$t_i$をとり、隠れている場合は ---- を独立して、$q_i$ を$i=1,\ldots,n$ で検出する。 シーカーは検出までの期待時間を最大化し、サーチは最小化することを目的としている。 各プレイヤーに最適な戦略が存在することを証明します。 特に、隠蔽者の最適混合戦略はゼロではない確率で各場所に隠れており、探索者の最適混合戦略は、最大$n$の単純な検索シーケンスで構築することができる。 我々は,各プレイヤーの最適戦略を計算するアルゴリズムを開発し,探索開始時に位置選好を付与しない単純な隠れ戦略と比較する。

関連論文リスト

• Rectangle Search: An Anytime Beam Search (Extended Version) [9.59799149404787]
  任意の検索アルゴリズムは、(潜在的に最適でない)解をできるだけ早く見つけようとする。 本稿では,ビーム探索に基づく新しい長方形探索法を提案する。
  論文  参考訳（メタデータ） (2023-12-19T19:50:45Z)
• Active Ranking of Experts Based on their Performances in Many Tasks [72.96112117037465]
  我々は、dタスクのパフォーマンスに基づいて、n名のエキスパートをランク付けする問題を考察する。 我々は,各専門家のペアに対して,各タスクにおいて他方よりも優れているという,単調な仮定を定めている。
  論文  参考訳（メタデータ） (2023-06-05T06:55:39Z)
• Strategizing against Learners in Bayesian Games [74.46970859427907]
  プレイヤーの1人である学習者が無学習の学習戦略を採用する2人プレイヤゲームについて検討した。 一般のベイズゲームでは,学習者と学習者の双方の報酬の支払いが,そのタイプに依存する可能性がある。
  論文  参考訳（メタデータ） (2022-05-17T18:10:25Z)
• Adaptive Multi-Goal Exploration [118.40427257364729]
  我々は、AdaGoalが$epsilon$-optimal goal-conditioned policyを学習する目的を達成するためにどのように使えるかを示す。 AdaGoalは、ゴール条件の深い強化学習のための既存の手法の高レベルなアルゴリズム構造に固定されている。
  論文  参考訳（メタデータ） (2021-11-23T17:59:50Z)
• Optimizing $\alpha\mu$ [7.715389335184684]
  $alphamu$は、Perfect Information Monte Carlo searchのデフォルトである戦略融合と非局所性の2つを修復する検索アルゴリズムである。 本稿では、Bridgeのゲームに$alphamu$を最適化し、無駄な計算を避ける。
  論文  参考訳（メタデータ） (2021-01-29T15:20:03Z)
• Faster Algorithms for Optimal Ex-Ante Coordinated Collusive Strategies in Extensive-Form Zero-Sum Games [123.76716667704625]
  我々は,不完全情報ゼロサム拡張形式ゲームにおいて,対戦相手と対決する2人の選手のチームにとって最適な戦略を見つけることの課題に焦点をあてる。 この設定では、チームができる最善のことは、ゲーム開始時の関節(つまり相関した)確率分布から潜在的にランダム化された戦略(プレイヤー1人)のプロファイルをサンプリングすることである。 各プロファイルにランダム化されるのはチームメンバーの1人だけであるプロファイルのみを用いることで、そのような最適な分布を計算するアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2020-09-21T17:51:57Z)
• Object Tracking by Least Spatiotemporal Searches [30.517911630100976]
  5つの探索戦略を実験で比較し、IHMが最も効率的であることが検証され、最大1/3のコストを節約できる。 この結果から,「中間時点の探索はコストを節約できる」という証拠が得られた。
  論文  参考訳（メタデータ） (2020-07-18T00:17:55Z)
• Best-First Beam Search [78.71330480725668]
  本研究では,ビームサーチの標準実装を10倍高速に実現可能であることを示す。 ダウンストリーム性能の面でも同様に有益な探索バイアスを有するBest-First Beam Searchのメモリ再生版を提案する。
  論文  参考訳（メタデータ） (2020-07-08T05:56:01Z)
• Efficient exploration of zero-sum stochastic games [83.28949556413717]
  ゲームプレイを通じて,ゲームの記述を明示せず,託宣のみにアクセス可能な,重要で一般的なゲーム解決環境について検討する。 限られたデュレーション学習フェーズにおいて、アルゴリズムは両方のプレイヤーのアクションを制御し、ゲームを学習し、それをうまくプレイする方法を学習する。 私たちのモチベーションは、クエリされた戦略プロファイルの支払いを評価するのにコストがかかる状況において、利用可能性の低い戦略を迅速に学習することにあります。
  論文  参考訳（メタデータ） (2020-02-24T20:30:38Z)

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

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