Optimal Sensor and Actuator Selection for Factored Markov Decision Processes: Complexity, Approximability and Algorithms

2024-07-10 · Jayanth Bhargav, Mahsa Ghasemi, Shreyas Sundaram

Factored Markov Decision Processes (fMDPs) are a class of Markov Decision Processes (MDPs) in which the states (and actions) can be factored into a set of state (and action) variables and can be encoded compactly using a factored representation. In this paper, we consider a setting where the state of the fMDP is not directly observable, and the agent relies on a set of potential sensors to gather information. Each sensor has a selection cost and the designer must select a subset of sensors under a limited budget. We formulate the problem of selecting a set of sensors for fMDPs (under a budget) to maximize the infinite-horizon discounted return provided by the optimal policy. We show the fundamental result that it is NP-hard to approximate this problem to within any non-trivial factor. Our inapproximability results for optimal sensor selection also extend to a general class of Partially Observable MDPs (POMDPs). We then study the dual problem of budgeted actuator selection (at design-time) to maximize the expected return under the optimal policy. Again, we show that it is NP-hard to approximate this problem to within any non-trivial factor. Furthermore, with explicit examples, we show the failure of greedy algorithms for both the sensor and actuator selection problems and provide insights into the factors that cause these problems to be challenging. Despite this, through extensive simulations, we show the practical effectiveness and near-optimal performance of the greedy algorithm for actuator and sensor selection in many real-world and randomly generated instances.

📄 PDF Abstract BibTeX arXiv:2407.07310

Code (0)

등록된 구현이 없습니다.

Methods 이 논문이 사용한 방법론

SET Dynamic Sparse Training method where weight mask is updated randomly periodically

Towards Understanding Sensor and Control Nodes Selection in Nonlinear Dynamic Systems: Lyapunov Theory Meets Branch-and-Bound

2020-12-27 · Sebastian A. Nugroho, Ahmad F. Taha

Sensor and actuator selection problems (SASP) are some of the core problems in dynamic systems design and control. These problems correspond to determining the optimal selection of sensors (measurements) or actuators (co…

valid

Proximal algorithms for large-scale statistical modeling and sensor/actuator selection

2018-07-04 · Armin Zare, Hesameddin Mohammadi, Neil K. Dhingra, Tryphon T. Georgiou 외

Several problems in modeling and control of stochastically-driven dynamical systems can be cast as regularized semi-definite programs. We examine two such representative problems and show that they can be formulated in a…

Towards Minimax Optimal Reinforcement Learning in Factored Markov Decision Processes

2020-06-24 · NeurIPS 2020 12 · Yi Tian, Jian Qian, Suvrit Sra

We study minimax optimal reinforcement learning in episodic factored Markov decision processes (FMDPs), which are MDPs with conditionally independent transition components. Assuming the factorization is known, we propose…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Reinforcement Learning in Factored MDPs: Oracle-Efficient Algorithms and Tighter Regret Bounds for the Non-Episodic Setting

2020-02-06 · NeurIPS 2020 12 · Ziping Xu, Ambuj Tewari

We study reinforcement learning in non-episodic factored Markov decision processes (FMDPs). We propose two near-optimal and oracle-efficient algorithms for FMDPs. Assuming oracle access to an FMDP planner, they enjoy a B…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Efficient Reinforcement Learning in Factored MDPs with Application to Constrained RL

2020-08-31 · ICLR 2021 1 · Xiaoyu Chen, Jiachen Hu, Lihong Li, Li-Wei Wang

Reinforcement learning (RL) in episodic, factored Markov decision processes (FMDPs) is studied. We propose an algorithm called FMDP-BF, which leverages the factorization structure of FMDP. The regret of FMDP-BF is shown …

reinforcement-learning Reinforcement Learning (RL)