# Reinforcement Learning with Action-Triggered Observations

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 21 of its 47 references that are in the map.
- First posted on arXiv 2 Oct 2025.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

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

- [Hindsight Experience Replay](https://mlsanity.com/paper/1707.01495/) (2017)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Deep Recurrent Q-Learning for Partially Observable MDPs](https://mlsanity.com/paper/1507.06527/) (2015)
- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Delay and Cooperation in Nonstochastic Bandits](https://mlsanity.com/paper/1602.04741/) (2016)
- [Sample-Efficient Reinforcement Learning of Undercomplete POMDPs](https://mlsanity.com/paper/2006.12484/) (2020)
- [Reinforcement Learning with Random Delays](https://mlsanity.com/paper/2010.02966/) (2020)
- [An Optimal Algorithm for Adversarial Bandits with Arbitrary Delays](https://mlsanity.com/paper/1910.06054/) (2019)
- [A PAC RL Algorithm for Episodic POMDPs](https://mlsanity.com/paper/1605.08062/) (2016)
- [Active Measure Reinforcement Learning for Observation Cost Minimization](https://mlsanity.com/paper/2005.12697/) (2020)
- [Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiency](https://mlsanity.com/paper/2204.09787/) (2022)
- [Delayed Reinforcement Learning by Imitation](https://mlsanity.com/paper/2205.05569/) (2022)
- [A Unified Analysis of Nonstochastic Delayed Feedback for Combinatorial Semi-Bandits, Linear Bandits, and MDPs](https://mlsanity.com/paper/2305.08629/) (2023)
- [No Weighted-Regret Learning in Adversarial Bandits with Delays](https://mlsanity.com/paper/2103.04550/) (2021)
- [Act-Then-Measure: Reinforcement Learning for Partially Observable Environments with Active Measuring](https://mlsanity.com/paper/2303.08271/) (2023)
- [Exploiting Submodular Value Functions For Scaling Up Active Perception](https://mlsanity.com/paper/2009.09696/) (2020)
- [Capacity-Constrained Online Learning with Delays: Scheduling Frameworks and Regret Trade-offs](https://mlsanity.com/paper/2503.19856/) (2025)
- [Exploiting Curvature in Online Convex Optimization with Delayed Feedback](https://mlsanity.com/paper/2506.07595/) (2025)
- [Online Reinforcement Learning with Uncertain Episode Lengths](https://mlsanity.com/paper/2302.03608/) (2023)
- [Intermittently Observable Markov Decision Processes](https://mlsanity.com/paper/2302.11761/) (2023)
- [OCMDP: Observation-Constrained Markov Decision Process](https://mlsanity.com/paper/2411.07087/) (2024)

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

- [Capacity-Constrained Online Convex Optimization with Delayed Feedback](https://mlsanity.com/paper/2606.11711/) (2026)

## Abstract (arXiv)

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 widetildeO(√Kd3(1-γ)-3) for episodic learning with geometrically distributed horizons, where K is the number of episodes, d the feature dimension, and γ the discount factor (episode continuation probability), matching the known rate for linear MDPs with full observability.