論文の概要: A Markov Decision Process Framework for Efficient and Implementable
Contact Tracing and Isolation
- arxiv url: http://arxiv.org/abs/2112.15547v2
- Date: Fri, 14 Jan 2022 04:05:56 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-02 19:03:52.611105
- Title: A Markov Decision Process Framework for Efficient and Implementable
Contact Tracing and Isolation
- Title(参考訳): 効率よく実装可能なコンタクトトラクションと分離のためのマルコフ決定プロセスフレームワーク
- Authors: George Li, Arash Haddadan, Ann Li, Madhav Marathe, Aravind Srinivasan,
Anil Vullikanti, Zeyu Zhao
- Abstract要約: 本稿では,接触追跡の問題点を定式化するためのマルコフ決定プロセスフレームワークを提案する。
このアルゴリズムが、孤立した個体数を制限しながら、流行曲線を曲げるのにどのように役立つかを示す。
- 参考スコア(独自算出の注目度): 18.740978811360783
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Efficient contact tracing and isolation is an effective strategy to control
epidemics. It was used effectively during the Ebola epidemic and successfully
implemented in several parts of the world during the ongoing COVID-19 pandemic.
An important consideration in contact tracing is the budget on the number of
individuals asked to quarantine -- the budget is limited for socioeconomic
reasons. In this paper, we present a Markov Decision Process (MDP) framework to
formulate the problem of using contact tracing to reduce the size of an
outbreak while asking a limited number of people to quarantine. We formulate
each step of the MDP as a combinatorial problem, MinExposed, which we
demonstrate is NP-Hard; as a result, we develop an LP-based approximation
algorithm. Though this algorithm directly solves MinExposed, it is often
impractical in the real world due to information constraints. To this end, we
develop a greedy approach based on insights from the analysis of the previous
algorithm, which we show is more interpretable. A key feature of the greedy
algorithm is that it does not need complete information of the underlying
social contact network. This makes the heuristic implementable in practice and
is an important consideration. Finally, we carry out experiments on simulations
of the MDP run on real-world networks, and show how the algorithms can help in
bending the epidemic curve while limiting the number of isolated individuals.
Our experimental results demonstrate that the greedy algorithm and its variants
are especially effective, robust, and practical in a variety of realistic
scenarios, such as when the contact graph and specific transmission
probabilities are not known. All code can be found in our GitHub repository:
https://github.com/gzli929/ContactTracing.
- Abstract(参考訳): 効果的な接触追跡と隔離は疫病の予防に有効な戦略である。
エボラ出血熱の流行時に効果的に使われ、進行中の新型コロナウイルスのパンデミックで世界のいくつかの地域で成功を収めた。
接触追跡における重要な考慮事項は、隔離を求める人数の予算であり、社会経済的な理由から予算は限られている。
本稿では,限られた人数に隔離を依頼しながら,接触追跡による感染拡大の低減を図ったマルコフ決定プロセス(MDP)フレームワークを提案する。
我々は,MPPの各ステップを組合せ問題であるMinExposedとして定式化し,NP-Hardを証明し,その結果,LPに基づく近似アルゴリズムを開発した。
このアルゴリズムはMinExposedを直接解くが、情報制約のため実世界では実用的ではないことが多い。
この目的のために,先行アルゴリズムの分析から得られた洞察に基づいて,より解釈可能な欲望的アプローチを開発する。
greedyアルゴリズムの重要な特徴は、基盤となるソーシャルコンタクトネットワークの完全な情報を必要としないことである。
これにより、ヒューリスティックな実装が可能となり、重要な考慮事項となる。
最後に,実世界のネットワーク上で実行されるmdpのシミュレーション実験を行い,そのアルゴリズムが分離個体数を制限しながら流行曲線を曲げる上でどのように役立つかを示す。
実験の結果,グリーディアルゴリズムとその変種は,接触グラフや特定の伝達確率が不明な場合など,様々な現実的なシナリオにおいて,特に有効で堅牢で実用的であることが示された。
すべてのコードはgithubリポジトリにある。 https://github.com/gzli929/contacttracing。
関連論文リスト
- Offline Oracle-Efficient Learning for Contextual MDPs via Layerwise Exploration-Exploitation Tradeoff [12.847844923530577]
実現可能性前提の下で, CMDP からオフライン密度推定への削減を提案する。
本アルゴリズムの特筆すべき特徴は,CMDPの層状構造に対応するため,層状探索・探索トレードオフの設計である。
論文 参考訳(メタデータ) (2024-05-28T03:47:41Z) - Online POMDP Planning with Anytime Deterministic Guarantees [11.157761902108692]
不確実性の下での計画は、部分的に観測可能なマルコフ決定プロセス(POMDP)を用いて数学的に定式化できる
POMDPの最適計画を見つけるには計算コストがかかり、小さなタスクにのみ適用可能である。
簡便な解と理論的に最適な解との決定論的関係を導出する。
論文 参考訳(メタデータ) (2023-10-03T04:40:38Z) - A Fast Algorithm for Moderating Critical Nodes via Edge Removal [19.130541561303293]
対象ノードの情報集中度を最小限に抑えるために,ネットワークから$k$エッジを除去する問題について検討する。
ランダムウォークに基づくシュア補数近似や高速和推定などの新しい手法を用いて、3つの近似グリードアルゴリズムを提案する。
理論的解析を補完するため、100万以上のノードを持つ合成および実ネットワークに関する包括的な実験を行う。
論文 参考訳(メタデータ) (2023-09-09T13:54:34Z) - Communication-Efficient Decentralized Federated Learning via One-Bit
Compressive Sensing [52.402550431781805]
分散連合学習(DFL)は、様々なアプリケーションにまたがる実用性によって人気を博している。
集中型バージョンと比較して、DFLの多数のノード間で共有モデルをトレーニングするのはより難しい。
我々は,iADM (iexact alternating direction method) の枠組みに基づく新しいアルゴリズムを開発した。
論文 参考訳(メタデータ) (2023-08-31T12:22:40Z) - Reinforcement Learning with a Terminator [80.34572413850186]
我々は, TerMDP のパラメータを学習し, 推定問題の構造を活用し, 状態ワイドな信頼境界を提供する。
我々はこれらを用いて証明可能な効率のよいアルゴリズムを構築し、終端を考慮し、その後悔を抑える。
論文 参考訳(メタデータ) (2022-05-30T18:40:28Z) - Learning to Detect Critical Nodes in Sparse Graphs via Feature Importance Awareness [53.351863569314794]
クリティカルノード問題(CNP)は、削除が残余ネットワークのペア接続性を最大に低下させるネットワークから臨界ノードの集合を見つけることを目的としている。
本研究は,ノード表現のための特徴重要度対応グラフアテンションネットワークを提案する。
ダブルディープQネットワークと組み合わせて、初めてCNPを解くエンドツーエンドのアルゴリズムを作成する。
論文 参考訳(メタデータ) (2021-12-03T14:23:05Z) - Efficient Algorithms for Finite Horizon and Streaming Restless
Multi-Armed Bandit Problems [30.759279275710078]
インデックスベースのソリューションを計算するための新しいスケーラブルなアプローチを提案します。
コストのかかる有限地平線問題を解くことなく,指数減衰をキャプチャするアルゴリズムを提供する。
当社のアルゴリズムは、これらのタスクにおける既存の方法よりも150倍以上のスピードアップを実現し、パフォーマンスを損ないません。
論文 参考訳(メタデータ) (2021-03-08T13:10:31Z) - Sample-Efficient Reinforcement Learning via Counterfactual-Based Data
Augmentation [15.451690870640295]
医療などのいくつかのシナリオでは、通常、各患者に利用可能なレコードはごくわずかであり、現在の強化学習アルゴリズムの適用を妨げる。
構造因果モデル(SCM)を利用して状態ダイナミクスをモデル化する,データ効率の高いRLアルゴリズムを提案する。
本研究は, 軽度条件下では反実結果が識別可能であり, 反実に基づく拡張データセット上のq学習が最適値関数に収束することを示す。
論文 参考訳(メタデータ) (2020-12-16T17:21:13Z) - Resource Allocation in Multi-armed Bandit Exploration: Overcoming
Sublinear Scaling with Adaptive Parallelism [107.48538091418412]
腕の引っ張りに様々な量の資源を割り当てることができる分割可能な資源にアクセス可能な場合,マルチアームの帯状地における探索について検討する。
特に、分散コンピューティングリソースの割り当てに重点を置いており、プル毎により多くのリソースを割り当てることで、結果をより早く得ることができます。
論文 参考訳(メタデータ) (2020-10-31T18:19:29Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳(メタデータ) (2020-09-28T15:22:24Z) - Sample-Efficient Reinforcement Learning of Undercomplete POMDPs [91.40308354344505]
この研究は、これらの硬度障壁が、部分観測可能決定過程(POMDP)の豊かで興味深いサブクラスに対する効率的な強化学習を妨げないことを示している。
提案手法は, 観測回数が潜伏状態の数よりも大きく, 探索が学習に不可欠であり, 先行研究と区別できるような, エピソード有限不完全POMDPに対するサンプル効率アルゴリズムOOM-UCBを提案する。
論文 参考訳(メタデータ) (2020-06-22T17:58:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。