📊 statistics

Reinforcement Learning with Action-Triggered Observations

This paper introduces Action-Triggered Sporadically Traceable Markov Decision Processes (ATST-MDPs), a framework where full state observations occur stochastically based on chosen actions, and proposes an optimistic algorithm (ATST-LSVI-UCB) that achieves optimal regret bounds for linear MDPs by leveraging action-sequence commitments between sporadic observations.

Original authors: Alexander Ryabchenko, Wenlong Mou

Published 2026-06-11

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Alexander Ryabchenko, Wenlong Mou

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are playing a video game where your character is walking through a foggy forest. In a standard game, every time you take a step, the screen updates, and you see exactly where you are. But in this new framework, the screen only updates occasionally.

Here's the twist: You control how often the screen updates.

Some moves you make might be like shouting loudly, which clears the fog immediately but might be tiring or risky. Other moves might be like tiptoeing, which is safe but leaves you in the dark for a long time. This is the core idea of the paper: Action-Triggered Sporadically Traceable Markov Decision Processes (ATST-MDPs).

Here is a breakdown of the paper's concepts using simple analogies:

1. The Problem: The "Foggy Forest"

In many real-world situations (like a doctor deciding on a treatment or a trader managing a portfolio), you can't always see the full picture.

Standard AI: Assumes you see the world perfectly after every move.
The Reality: Sometimes you have to pay a cost (time, money, risk) to get a clear view.
The Paper's Insight: The paper creates a mathematical model where the choice of action determines the chance of getting a clear view. If you choose a "loud" action, you get a "data burst" (a clear snapshot of the world). If you choose a "quiet" action, you stay in the fog.

2. The Strategy: "Committing to a Path"

Since you can't see the world every second, you can't react instantly to every change. So, how do you make decisions?

The authors suggest a clever trick: Instead of thinking one step at a time, think in "chunks" or "sequences."

The Analogy: Imagine you are driving a car in heavy fog. You can't see the road ahead, but you know that if you press the horn (a specific action), a lighthouse beam will flash, revealing the road for a moment.
The Strategy: Between two lighthouse flashes, you don't panic. You commit to a specific driving plan (e.g., "I will turn left, then go straight for 10 seconds, then turn right"). You stick to this plan until the next flash reveals your new position.
The Paper's Math: They prove that even though the world is foggy, you can treat these "chunks" of actions as a single, giant decision. This turns a confusing, partial-view problem into a clear, step-by-step problem.

3. The "Magic Map" (Linear Representation)

The paper gets technical here, but the concept is simple. Usually, figuring out the best path in a foggy world is impossible because there are too many possibilities.

However, the authors assume the world follows a "Linear" structure (a fancy way of saying the rules are predictable and can be described by a simple formula).

The Analogy: Imagine the foggy forest isn't random chaos; it's built like a giant Lego set. Even if you can't see the whole castle, if you know the shape of the bricks (the "features"), you can predict how the castle will look when you add a new brick, even without seeing it.
The Result: They created a "Magic Map" (a feature map) that lets the AI predict the value of its long-term plans using simple math (regression), just like a standard video game AI would, even though it's playing in the fog.

4. The Algorithm: "Optimistic Explorer"

The paper introduces an algorithm called ATST-LSVI-UCB.

How it works: The AI is "optimistic." When it doesn't know what will happen if it takes a certain path, it assumes the best-case scenario to encourage itself to try it.
The Goal: It tries to learn the "Magic Map" and the best "chunks" of actions as fast as possible.
The Result: They proved mathematically that this AI learns almost as fast as an AI that could see the world perfectly, even though it only gets glimpses.

5. The Experiments: Two Different Forests

The authors tested their idea on two simulated games:

RiverSwim: A game where you have to swim upstream to get a big reward.
- Result: Surprisingly, less frequent updates helped the AI learn faster. Why? Because being in the fog forced the AI to commit to a long plan (swimming upstream) without second-guessing itself every second.
RiverBalance: A game where you have to stay in the center of a moving river.
- Result: More frequent updates helped. Why? Because staying balanced requires constant, tiny corrections. If you are in the fog too long, you drift off course.

Summary

This paper introduces a new way for AI to learn when it can't see everything. It shows that if you can choose when to look, you can turn a confusing, foggy problem into a series of clear, manageable plans. They proved that with the right math, an AI can learn to navigate these foggy worlds just as efficiently as one that sees everything clearly.

Technical Summary: Reinforcement Learning with Action-Triggered Observations

1. Problem Definition

The paper addresses a specific class of Partially Observable Markov Decision Processes (POMDPs) where the availability of state observations is not exogenous or fixed, but rather action-triggered. In standard RL, an agent observes the new state after every action. In many practical scenarios (e.g., clinical diagnostics, financial trading), obtaining a state observation is costly, unreliable, or requires a specific action to trigger.

The authors formalize this setting as Action-Triggered Sporadically Traceable Markov Decision Processes (ATST-MDPs).

Mechanism: When an agent in state $s$ executes action $a$ , it receives a reward and the environment transitions to $s'$ . Crucially, $s'$ is not always observed. With probability $\beta(a)$ , an "observational event" (data-burst) occurs, revealing $s'$ and the cumulative reward since the last burst. With probability $1-\beta(a)$ , no state feedback is provided.
Challenge: The agent must simultaneously optimize the control policy and decide when to trigger observations (by choosing actions with higher $\beta(a)$ ) to reduce uncertainty, balancing the cost of information acquisition against control performance.
Distinction: Unlike standard POMDPs where observations are noisy but frequent, or RL with exogenous delays where feedback is simply late, ATST-MDPs feature endogenous delays where the agent's action choices directly determine the frequency of state revelation.

2. Methodology

2.1 Augmented State Space and Bellman Equations

To handle partial observability, the authors define an augmented state space $\mathcal{X} = \mathcal{S} \times \mathcal{A}^{<\infty}$ . An augmented state $x = (s_1, a_1, \dots, a_n)$ consists of the last observed state $s_1$ and the sequence of actions taken since that observation.

Sufficiency: The augmented state serves as a sufficient statistic for the history, allowing the problem to be treated as a fully observed MDP on $\mathcal{X}$ .
Dynamics: The transition on $\mathcal{X}$ is a mixture: with probability $\beta(a)$ , the state resets to the new observed state $s'$ ; with probability $1-\beta(a)$ , the action sequence is appended ( $x \leftarrow x \cdot a$ ).
Bellman Equations: The authors derive Bellman optimality equations for value functions $V^\pi$ and $Q^\pi$ on this augmented space, proving the existence of an optimal augmented policy $\pi^*$ .

2.2 Action-Sequence Reformulation

Recognizing that the augmented state space branches infinitely, the authors propose a reformulation based on the renewal structure of data-bursts. Instead of deciding action-by-action, the agent commits to an action-sequence $a \in \mathcal{A}^\mathbb{N}$ at each data-burst, executing it until the next observation occurs.

This transforms the problem into a decision process over $(\mathcal{S}, \mathcal{A}^\mathbb{N})$ .
The value function $K^\pi(s, a)$ represents the expected discounted reward accumulated from state $s$ by executing sequence $a$ until the next data-burst, plus the continuation value from the revealed state.

2.3 Linear Representation under Linear MDP Assumption

To make the infinite-dimensional action-sequence space tractable, the paper assumes a Linear MDP structure (Assumption 4.1), where transition kernels and rewards are linear in a feature map $\phi(s, a)$ .

Key Insight: Under this assumption, the action-sequence value function $K^\pi$ admits a linear representation in a finite-dimensional feature map $\psi: \mathcal{S} \times \mathcal{A}^\mathbb{N} \to \mathbb{R}^{2d}$ .
Construction: The feature map $\psi$ is constructed using action-matrices $M_a$ (derived from the transition dynamics) and observation probabilities $\beta_a$ . Specifically, $\psi$ encodes the evolution of features over the action sequence and the probability of data-bursts occurring at each step.
Result: $K^\pi(s, a) = \langle \psi(s, a), v^\pi_{1,2} \rangle$ , where $v^\pi_{1,2}$ is a policy-dependent vector. This allows the use of standard regression-based methods despite the infinite action space.

2.4 Estimation and Learning Algorithm

The paper proposes ATST-LSVI-UCB (Action-Triggered Sporadically Traceable Least-Squares Value Iteration with Upper Confidence Bounds).

Feature Estimation: Since the true feature map $\psi$ is unknown, the algorithm estimates the underlying action-matrices $M_a$ and observation probabilities $\beta_a$ from exploratory data using ridge regression and empirical means. Theorem 4.6 and Corollary 4.9 provide non-asymptotic sample complexity bounds for constructing an $\epsilon$ -admissible approximation of $\psi$ .
Algorithm: The algorithm operates in episodes with geometric horizons. It performs backward value iteration on the estimated feature map to compute optimistic value estimates (using UCB bonuses) and executes greedy action-sequences.
Optimization: While the action space is infinite, the optimization $\max_a K(s, a)$ is performed over the compact image of the feature map. In practice, this can be approximated by restricting to finite-depth or eventually periodic sequences.

3. Key Contributions

Formalization of ATST-MDPs: A novel framework for RL where observation availability is a function of the chosen action, bridging the gap between standard MDPs and general POMDPs.
Theoretical Foundations: Derivation of Bellman equations on the augmented state space and proof of optimal policy existence.
Linear Representation: Demonstration that under the linear MDP assumption, the value function over action-sequences is linear in a finite-dimensional feature map, enabling efficient learning.
Algorithm and Regret Bounds: Proposal of ATST-LSVI-UCB, an optimistic value iteration algorithm. The authors prove a regret bound of $\tilde{O}(\sqrt{d^3 K (1-\gamma)^{-3}})$ for episodic learning, matching the known optimal rate for fully observable linear MDPs.
Sample Complexity: Establishment of sample complexity guarantees for estimating the action-sequence feature map from data, showing it is polynomial in dimension $d$ and independent of the state space size $|\mathcal{S}|$ .

4. Results

Theoretical: The regret bound matches the state-of-the-art for linear MDPs with full observability, despite the added complexity of partial observability and action-triggered delays. The bound scales with the feature dimension $d$ , number of episodes $K$ , and the inverse of the discount factor $(1-\gamma)$ .
Empirical: Experiments on two tabular environments, RiverSwim (exploration-heavy) and RiverBalance (stabilization-heavy), demonstrate the algorithm's viability.
- In RiverSwim, sparse observations (low $\beta$ ) surprisingly accelerated convergence by encouraging longer open-loop commitments (exploration).
- In RiverBalance, frequent observations (high $\beta$ ) yielded higher rewards, as the task required state-dependent corrections to maintain stability.
- The results highlight that the optimal observation frequency is task-dependent.

5. Significance and Claims

The paper claims to provide a theoretical foundation for reinforcement learning in environments with action-triggered state observations. Its significance lies in:

Bridging Gaps: It addresses a specific, practically relevant class of POMDPs (active perception, costly sensing) that general POMDP methods struggle with due to computational intractability.
Tractability: By leveraging the renewal structure induced by data-bursts and the linear MDP assumption, it transforms an intractable partial observability problem into a tractable linear regression problem.
Optimality: It achieves regret rates comparable to fully observable settings, suggesting that the "cost" of sporadic observability can be mitigated if the observation mechanism is understood and leveraged.
Reward-Free Estimation: The feature map estimation is reward-free, meaning the structural learning of the environment (dynamics and observation probabilities) can be decoupled from the specific reward function, allowing for flexible policy adaptation.

The authors note that future work should focus on designing efficient approximation schemes for the infinite action-sequence optimization and developing fully online algorithms that adaptively refine feature estimates without pre-collected exploratory data.