Reinforcement Learning with Action-Triggered Observations

We introduce Action-Triggered Sporadically Traceable Markov Decision Processes (ATST-MDPs), a reinforcement learning framework for partial observability in which full state observations occur stochastically at each step, with probability determined by the chosen action. We derive Bellman equations tailored to this setting and establish the existence of an optimal policy. Exploiting the fact that sporadic observations reveal the full state, we provide an equivalent formulation in which agents commit to action-sequences between consecutive observations. Under the linear MDP assumption, we show that the value function over such action-sequences admits a linear representation in a finite-dimensional feature map, enabling standard regression-based methods. As an application, we derive ATST-LSVI-UCB, an optimistic algorithm achieving regret $\widetilde{O}(\sqrt{Kd^3(1-\gamma)^{-3}})$ for episodic learning with geometrically distributed horizons, where $K$ is the number of episodes, $d$ the feature dimension, and $\gamma$ the discount factor (episode continuation probability), matching the known rate for linear MDPs with full observability.

This paper studies reinforcement learning in settings where an agent does not always observe the next state after taking an action. Such situations arise in domains like healthcare and finance, where reliable information may require actions that trigger tests, measurements, or other costly observations. We introduce a model in which each action has its own probability of revealing the next state. We show that, between observations, the agent can be viewed as planning a sequence of actions. This structure leads to an efficient learning algorithm with strong guarantees, benchmarked against the best policy subject to the same observation constraints.