Reinforcement Learning with Action-Triggered Observations

Alexander Ryabchenko, Wenlong Mou

Executive Summary

This paper introduces Action-Triggered Sporadically Traceable Markov Decision Processes (ATST-MDPs), a novel reinforcement learning framework designed for environments where state observations are not guaranteed but are instead triggered stochastically by the agent's actions. By leveraging the property that these sporadic observations reveal the full state when they do occur, the authors develop an algorithm that achieves the same theoretical statistical efficiency—measured by regret—as reinforcement learning with full observability.

Introduction and Motivation

In standard Reinforcement Learning (RL), theoretical models typically assume the agent observes the environment's true state after every single action. In real-world applications, however, this is rarely the case. Medical diagnostic tests can be expensive or risky; sensors on a deep-sea rover might fail or be deactivated to conserve power; and financial traders often only receive high-frequency data if they pay a premium.

These scenarios traditionally fall under Partially Observable MDPs (POMDPs), which are notoriously difficult to solve and often computationally and statistically intractable without highly specific assumptions. This paper identifies a practical middle ground: what if observations are sparse, but when they do happen, they reveal the full, true state? Specifically, the authors tackle the "action-triggered" regime, where the agent's choice of action directly determines the probability of receiving a state update.

Methodology

To bridge the gap between partial and full observability, the authors employ three key technical innovations:

  1. Augmented State Space: Because the agent does not observe the state at every step, it must track the last observed state alongside every action taken since that observation. This "history" effectively becomes the new state representation.
  2. Action-Sequence Reformulation: Instead of making step-by-step decisions in the dark, the problem is reframed. The agent commits to an infinite sequence of actions and executes them until a "data-burst" (a state observation) occurs. This exploits the "renewal" structure of the problem—every observation essentially resets the agent's uncertainty.
  3. Linear Representation: Under the common "Linear MDP" assumption (where transitions and rewards are linear functions of features), the authors prove that the value function for these long action-sequences is also linear. They construct a novel feature map ($\psi$) using a Neumann-series argument to represent these infinite sequences within finite dimensions.

Building on these foundations, the authors introduce ATST-LSVI-UCB, an optimistic value iteration algorithm that utilizes these sequence-based features to explore the environment efficiently.

Experimental Environments

The paper evaluates the proposed algorithm on two distinct simulation environments:

  • RiverSwim: A classic RL benchmark where an agent must swim against a current to reach a high-reward state. This environment is primarily used to test an agent's exploration capabilities.
  • RiverBalance: A newly introduced variant where the agent must maintain its position in the center of a chain of states while a current pulls it away. This environment tests "closed-loop" control, where frequent observations are typically necessary to stay balanced.

Key Insights

  • Observations as a "Reset": The core insight of the paper is that full-state observations act as renewal points. This prevents the "belief state" (the probability distribution over where the agent thinks it is) from compounding into an unmanageable mess, which is the primary hurdle in general POMDPs.
  • Endogenous vs. Exogenous Delays: Most prior work on delayed feedback treats the delay as an exogenous factor—something that happens to the agent. In ATST-MDPs, the delay is endogenous. The agent can strategically choose actions that are more likely to trigger an observation if it needs to reduce uncertainty.
  • The Exploration Paradox: In the RiverSwim experiments, the authors discovered a counterintuitive phenomenon: lower observation frequencies actually accelerated learning. Because the agent received infrequent updates, it was forced to commit to long sequences of "swim upstream" actions. This commitment helped it discover the distant high-reward state faster than an agent that constantly received updates and second-guessed its trajectory.

Theoretical and Empirical Results

  • Theoretical Optimality: The authors prove a regret bound of $\widetilde{O}(\sqrt{Kd^3(1-\gamma)^{-3}})$, where $K$ is the number of episodes, $d$ is the feature dimension, and $\gamma$ is the discount factor (episode continuation probability). Crucially, this matches the known optimal rate for linear MDPs with full observability. This demonstrates that statistical efficiency is not necessarily lost just because observations are sporadic.
  • Empirical Validation: In RiverSwim, the agent successfully learned the optimal policy across various observation probabilities. In RiverBalance, the agent's performance scaled gracefully: more frequent observations led to higher rewards (better balancing), but even with very sparse data, the algorithm successfully learned the best possible policy for that constrained regime.

Limitations and Future Work

  • The Optimization Oracle: The current algorithm assumes the existence of an "oracle" capable of finding the best action sequence from an infinite set. While the authors suggest using "eventually periodic" sequences to make this practical, developing a truly efficient, general-purpose optimizer for these sequences remains an open challenge.
  • Online Feature Estimation: The framework currently relies on an initial phase of exploratory data to estimate the feature map ($\psi$). A "fully online" version—where the feature map and the policy are learned simultaneously from scratch—would be a more robust, albeit more complex, solution.
  • Computational Complexity: While statistically efficient, the matrix inversions required for evaluating long action sequences could become a computational bottleneck in very high-dimensional feature spaces.

Summary updated

Abstract

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.
BibTeX
@inproceedings{ryabchenko2026reinforcement,
  author = {Alexander Ryabchenko and Wenlong Mou},
  title = {{Reinforcement Learning with Action-Triggered Observations}},
  booktitle = {International Conference on Machine Learning},
  year = {2026},
  url = {https://openreview.net/forum?id=jhNMY6jHJw},
}
Figure