[Question] Termination with timeout break the Markov assumption

[PierrePeng]

Question

I'm confuesed if it will break the Markov assumption in some tasks(e.g. navigation) which add timeout in termination term but not give sufficent time limit information in observation term.

[RandomOakForest]

Thank you for posting this. Terminating episodes with a timeout can break the Markov assumption if the time limit is not provided as part of the agent's observation. In tasks like navigation, simply enforcing a timeout without exposing the remaining time in the observation space leads to a situation where the agent is acting in a partially observable Markov decision process (POMDP) rather than a true Markov Decision Process (MDP).¹²

Why Timeouts Break the Markov Assumption

The Markov property requires that all information necessary to predict the next state (and reward) is fully captured in the current state representation. When an environment terminates due to a fixed step limit, but the agent's observation does not include how close it is to that limit, there will be latent state information (remaining timesteps) influencing state transitions that the agent cannot infer from its observations. This "hidden variable" leads to state aliasing, because multiple "identical" observations have different true next-state distributions depending on how much time remains.²³¹

Navigation and Timeout Terminations

In navigation tasks, a timeout might represent the agent failing to reach its goal within a certain number of steps. If the agent does not know how many steps are left before forced termination, it cannot condition its actions on this crucial piece of environment state. For example, it cannot distinguish whether it has one step left (requiring urgency) or many steps left (allowing a more exploratory policy).⁴¹²

Proper Handling to Preserve Markov Property

To maintain the Markov structure:

• Include remaining time/steps in the observation: This converts the time-dependent MDP to a time-augmented state, preserving full observability and compliance with the Markov property.¹²
• Alternative: If timeouts are only used for training convenience and not part of the environment's "real" dynamics, episodic data handling (e.g., bootstrapping from last state’s value rather than using it as a true terminal) can mitigate the issue, but the agent is still formally in a POMDP without remaining time in the observation.²¹

Key Takeaways

• Markov assumption is broken by timeouts if remaining time is not in the observation.
• This causes state aliasing, leading to learning instability or suboptimal policies.¹²
• Always provide time-to-termination (e.g., "remaining steps") to the agent's observation if episode limits are enforced in real tasks.

This is a great topic for our Discussions section. I will move your post there may you need further help, and for others to follow up.

Footnotes

1. https://arxiv.org/pdf/1712.00378.pdf ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶

2. https://ar5iv.labs.arxiv.org/html/1712.00378 ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶

3. https://www.ubishops.ca/wp-content/uploads/orouji20230108.pdf ↩

4. https://prl-theworkshop.github.io/prl2022-ijcai/papers/PRL2022_paper_24.pdf ↩