MDPs with a State Sensing Cost

Vansh Kapoor, Jayakrishnan Nair
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:1648-1656, 2026.

Abstract

In many practical sequential decision-making problems, tracking the state of the environment incurs a sensing/computation cost. In these settings, the agent’s interaction with its environment includes the additional component of deciding \emph{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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-kapoor26a, title = { MDPs with a State Sensing Cost }, author = {Kapoor, Vansh and Nair, Jayakrishnan}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {1648--1656}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/kapoor26a/kapoor26a.pdf}, url = {https://proceedings.mlr.press/v300/kapoor26a.html}, abstract = { In many practical sequential decision-making problems, tracking the state of the environment incurs a sensing/computation cost. In these settings, the agent’s interaction with its environment includes the additional component of deciding \emph{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. } }
Endnote
%0 Conference Paper %T MDPs with a State Sensing Cost %A Vansh Kapoor %A Jayakrishnan Nair %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-kapoor26a %I PMLR %P 1648--1656 %U https://proceedings.mlr.press/v300/kapoor26a.html %V 300 %X In many practical sequential decision-making problems, tracking the state of the environment incurs a sensing/computation cost. In these settings, the agent’s interaction with its environment includes the additional component of deciding \emph{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.
APA
Kapoor, V. & Nair, J.. (2026). MDPs with a State Sensing Cost . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:1648-1656 Available from https://proceedings.mlr.press/v300/kapoor26a.html.

Related Material