論文の概要: Strong and Compact Policies for Submodular Markov Decision Processes via LP-Based Submodular Orienteering
- arxiv url: http://arxiv.org/abs/2609.15539v1
- Date: Mon, 14 Sep 2026 13:26:08 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-16 12:40:38.845208
- Title: Strong and Compact Policies for Submodular Markov Decision Processes via LP-Based Submodular Orienteering
- Title（参考訳）: LP-based submodular Orienteeringによる部分モジュラーマルコフ決定過程の強コンパクト化
- Abstract要約: 本稿では,Sherali-Adams階層とRound-or-Cutのアイデアを用いた,サブモジュール指向性のためのLPベースの新しいアルゴリズムを提案する。
我々の保証は、準多項式時間対数近似(submodular Orienteering)の既知の準多項式時間対数近似に匹敵する。
- 参考スコア（独自算出の注目度）: 2.66418345185993
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Finding policies for Markov Decision Processes (MDPs) is a central problem in areas such as Reinforcement Learning and Operations Research. Here, we have to repeatedly choose an action that should be performed by an agent. Depending on the action and the current state of the agent, the agent collects a reward and randomly transitions into a new state. The goal is to maximize the reward in expectation over a finite time horizon of length $H$. We consider a recently introduced variant that generalizes the traditionally additive reward function in the model to a monotone submodular one, which allows for capturing a range of interesting applications. Without the stochastic component, this problem is equivalent to the Submodular Orienteering problem, where the goal is to find an $s$-$t$ walk in a directed graph maximizing a monotone submodular function under a length constraint. We present a novel LP-based algorithm for Submodular Orienteering using ideas from the Sherali-Adams hierarchy and Round-or-Cut. Our guarantees are comparable to the known quasi-polynomial time logarithmic approximation for Submodular Orienteering, but also extend to the setting of Submodular Markov Decision Processes. In the polynomial time regime, we present an $O(n^{\varepsilon})$-approximation (and $O(H^{\varepsilon})$ for Submodular MDPs) for every $\varepsilon >0$, where $n$ is the number of vertices, which was unknown even for Submodular Orienteering. Prior to our work, the best known approximation guarantee for Submodular MDPs had an approximation ratio linear in $H$. Beyond these algorithmic results, our methods reveal a trade-off between the approximation guarantee and the number of previously visited vertices on which an agent conditions its decision.
- Abstract（参考訳）: マルコフ決定プロセス(MDP)の政策の発見は、強化学習や運用研究などの分野における中心的な問題である。
ここでは、エージェントが実行すべきアクションを何度も選択する必要があります。
エージェントの動作と現在の状態に応じて、エージェントは報酬を集め、ランダムに新しい状態に遷移する。
目標は、長さ$H$の有限時間地平線上での期待の報酬を最大化することである。
最近導入された変種を考えると、モデルにおける伝統的加法的報酬関数をモノトン部分モジュラー関数に一般化し、様々な興味深い応用を捉えることができる。
確率成分がなければ、この問題は部分モジュラーオリエンテーリング問題と等価であり、この問題は長さ制約の下で単調部分モジュラー函数を最大化する有向グラフにおいて$s$-$t$ウォークを求めることである。
本稿では,Sherali-Adams階層とRound-or-Cutのアイデアを用いた,サブモジュール指向性のためのLPベースの新しいアルゴリズムを提案する。
我々の保証は、準多項式時間対数近似(submodular Orienteering)に匹敵するが、submodular Markov Decision Processesの設定にまで拡張される。
多項式時間系では、すべての$\varepsilon > 0$に対して$O(n^{\varepsilon})$-approximation (および$O(H^{\varepsilon})$)を提示する。
我々の研究に先立ち、劣モジュラ MDP の近似保証が最もよく知られているのは、$H$ の近似比であった。
これらのアルゴリズム結果の他に,提案手法は,近似保証とエージェントが決定を下す前に訪れた頂点の数とのトレードオフを明らかにする。
関連論文リスト
- Multinoulli Extension: A Lossless Continuous Relaxation for Partition-Constrained Subset Selection [60.07018090570548]
我々はパラメータフリーで、歪んだ局所探索法と同じ近似保証を実現できるMultinoulliSCGという新しいアルゴリズムを導入する。
また、分割制約に関する未探索オンラインサブセット選択問題に対して、Multinoulli-CGとMultinoulli-GAGAという2つの新しいオンラインアルゴリズムを提案する。
論文 参考訳（メタデータ） (2026-03-23T02:30:01Z) - Effective Policy Learning for Multi-Agent Online Coordination Beyond Submodular Objectives [64.16056378603875]
マルチエージェントオンライン協調問題に対する2つのポリシー学習アルゴリズムを提案する。
1つめの textttMA-SPL は MA-OC 問題に対して最適な$(fracce)$-approximation を達成することができる。
第2のオンラインアルゴリズムである textttMA-MPL は同じ近似比を同時に維持できる。
論文 参考訳（メタデータ） (2025-09-26T17:16:34Z) - Scalable Submodular Policy Optimization via Pruned Submodularity Graph [2.8672152503836]
強化学習(RL)では、エージェントが可能なアクションのセットを介して環境と対話し、未知の分布から報酬が生成される。
ここでの課題は、ある時間ステップ後の報酬が最大化されるような、最適な一連のアクションを見つけることである。
論文 参考訳（メタデータ） (2025-07-18T11:42:07Z) - Fair Submodular Cover [18.37610521373708]
フェア・サブモジュラー被覆 (FSC) の研究は、与えられた基底集合$U$, 単調部分モジュラー関数 $f:2UtomathbbR_ge 0$, しきい値$tau$ が与えられる。
まず、二項近似比を$(frac1epsilon, 1-O(epsilon))$とするFSCの離散アルゴリズムを導入する。
次に、$(frac1epsilon, 1-O(epsilon))$-を達成する連続アルゴリズムを示す。
論文 参考訳（メタデータ） (2024-07-05T18:37:09Z) - Submodular Reinforcement Learning [38.40138241424851]
強化学習(RL)では、状態の報酬は通常加法的と見なされ、マルコフの仮定に従って、それらは以前に訪れた状態に対して$textitindependent$である。
カバー範囲制御、実験設計、情報経路計画といった多くの重要な応用において、報酬は自然にリターンを減少させ、すなわち、それらの価値は以前に訪れた同様の状態から減少する。
減少するリターンをキャプチャするサブモジュール集合関数をモデルとした,より汎用的で非付加的(かつ履歴に依存しない)報酬を最適化するパラダイムである$textitsubmodular RL$ (SubRL)を提案する。
論文 参考訳（メタデータ） (2023-07-25T09:46:02Z) - Stochastic Submodular Maximization via Polynomial Estimators [13.498923494159312]
未知分布を持つ部分モジュラ函数のクラスに対する期待値として定義される部分モジュラ函数の最大化に焦点をあてる。
この形の単調関数に対して、グリーディ連続アルゴリズムは、推定を用いて、任意に$(1-1/e)近似63%の近似比(期待値)を得ることを示す。
論文 参考訳（メタデータ） (2023-03-17T13:32:33Z) - Randomized Greedy Learning for Non-monotone Stochastic Submodular
Maximization Under Full-bandit Feedback [98.29086113546045]
本稿では,非拘束型マルチアームバンディットのフルバンドフィードバックとサブモジュール性に対する報奨問題について検討する。
RGLは、サブモジュールおよび非サブモジュール設定において、他のフルバンド変種よりも経験的に優れていることを示す。
論文 参考訳（メタデータ） (2023-02-02T18:52:14Z) - Submodular + Concave [53.208470310734825]
第一次最適化法が凹関数の最大目的値に収束できることはよく確立されている。
本研究では、滑らかな函数凸体(英語版)の行列式を$F(x) = G(x) +C(x)$で始める。
このクラスの函数は、保証がないような凹凸函数と連続DR-部分モジュラ函数の両方の拡張である。
論文 参考訳（メタデータ） (2021-06-09T01:59:55Z) - The Power of Subsampling in Submodular Maximization [51.629656762796564]
このアプローチは,既存の手法よりもはるかに単純であるにもかかわらず,最適/最先端の結果をもたらすことを示す。
我々は,映像要約,位置情報要約,映画推薦タスクにおけるアルゴリズムの有効性を実証的に示す。
論文 参考訳（メタデータ） (2021-04-06T20:25:57Z) - Provably Efficient Reinforcement Learning for Discounted MDPs with
Feature Mapping [99.59319332864129]
本稿では,割引決定(MDP)のための強化学習について検討する。
本稿では,特徴写像を利用した新しいアルゴリズムを提案し,$tilde O(dsqrtT/ (1-gamma)2)$ regretを求める。
以上の結果から,提案した強化学習アルゴリズムは,最大1-γ-0.5$の係数でほぼ最適であることが示唆された。
論文 参考訳（メタデータ） (2020-06-23T17:08:54Z) - Regularized Submodular Maximization at Scale [45.914693923126826]
亜モジュラリティは本質的に多様性、カバレッジ、代表性の概念に関係している。
正規化部分モジュラ函数 $f = g ell$ を行列式部分モジュラ関数 $g$ とモジュラ関数 $ell$ の差分として最大化する手法を提案する。
論文 参考訳（メタデータ） (2020-02-10T02:37:18Z) - Streaming Submodular Maximization under a $k$-Set System Constraint [42.31117997337689]
非単調な部分モジュラーのストリーミングを非単調な部分モジュラーのストリーミングに変換する新しいフレームワークを提案する。
また,$k$ible $k$-setシステム制約を考慮したモノトンサブモジュールストリーミングのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-02-09T12:32:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。