# MDPs with a State Sensing Cost

arXiv: https://arxiv.org/abs/2505.03280 · HTML: https://mlsanity.com/paper/2505.03280/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 28 references that are in the map.
- First posted on arXiv 6 May 2025.

## Builds on (most cited first, 7 of 7)

- [Age of Information: An Introduction and Survey](https://mlsanity.com/paper/2007.08564/) (2020)
- [Incremental Pruning: A Simple, Fast, Exact Method for Partially Observable Markov Decision Processes](https://mlsanity.com/paper/1302.1525/) (2013)
- [Active Measure Reinforcement Learning for Observation Cost Minimization](https://mlsanity.com/paper/2005.12697/) (2020)
- [Act-Then-Measure: Reinforcement Learning for Partially Observable Environments with Active Measuring](https://mlsanity.com/paper/2303.08271/) (2023)
- [When to Sense and Control? A Time-adaptive Approach for Continuous-Time RL](https://mlsanity.com/paper/2406.01163/) (2024)
- [ICU-Sepsis: A Benchmark MDP Built from Real Medical Data](https://mlsanity.com/paper/2406.05646/) (2024)
- [Intermittently Observable Markov Decision Processes](https://mlsanity.com/paper/2302.11761/) (2023)

## Built on by (most cited first, 1 of 1)

- [When Should Agents Check External State? Budgeting Observations for Stored Intentions](https://mlsanity.com/paper/2609.37125/) (2026)

## Abstract (arXiv)

In many practical sequential decision-making problems, tracking the state of the environment incurs a sensing/communication/computation cost. In these settings, the agent's interaction with its environment includes the additional component of deciding when to sense the state, in a manner that balances the value associated with optimal (state-specific) actions and the cost of sensing. We formulate this as an expected discounted cost Markov Decision Process (MDP), wherein the agent incurs an additional cost for sensing its next state, but has the option to take actions while remaining `blind' to the system state. We pose this problem as a classical discounted cost MDP with an expanded (countably infinite) state space. While computing the optimal policy for this MDP is intractable in general, we derive lower bounds on the optimal value function, which allow us to bound the suboptimality gap of any policy. We also propose a computationally efficient algorithm SPI, based on policy improvement, which in practice performs close to the optimal policy. Finally, we benchmark against the state-of-the-art via a numerical case study.