I want to model a problem as an MDP and solve it with reinforcement learning algorithms. Suppose that the problem is episodic and it finishes at some point. However, termination occurs if either the agent reaches the goal, or the time/step limitation is passed. For example, in Grid World problem, the agent should reach the goal in at most 100 steps otherwise it will lose. Can I know how the states of the problems are defined in this problem? Should we define the value function for each cell in each time step?



1 Answer 1


If the time step limit is strictly part of the problem definition - i.e. it is not just for convenience of training - then the current time step should be considered part of the state. For grid world problems, the full state would be expressed as a $(location, time)$ tuple.

When solving using a value-based method, you could view that as having a value function $V(l,t)$, but it is more usual to consider that the state $s$ is multi-part $s = [l,t]$ and use the notation $V(s)$. Either way, then there are more unique states to find values for.

Note that you can, for convenience of training, ignore the time step limit the other way around, and just solve for optimal/minimum time steps. If that happens to be under the time limit you have set, then the agent can solve the problem as stated. This is often the easy training option.

Training with a strict time limit, where training episodes are forced to end with a timeout too, can be a far harder problem to solve, since initial nearly-random exploration will probably not discover a goal state such as exit from a maze.

You can ignore the strict interpretation and train without time step number as part of the state, yet still terminate/fail the episode after a fixed number of steps. This simplifies the state representation, although it then becomes a Partially Observable Markov Decision Process, usually just as difficult to solve and the value estimates will be inaccurate (on time step 99 out of 100, far away from the goal, a state will have same estimated value as step 1 out of 100). This inaccuracy might not affect the optimal policy much though, unless the environment allows a meaningful choice between quick low reward or longer-term higher reward.

OpenAI's Gym effectively treats MountainCar-V0 in this last way - time step is not returned as an observation, yet the episode ends after 200 episodes. Random agents can take far longer to succeed, making this an interesting challenge. In this case, adding the current time step to the state does not help very much (even though it would be strictly true for action state value estimates), because there is no variation where the agent could choose a different tactic to get a compromise score when it is close to running out of time. The challenge is mainly in finding a class of agent that will continue to reach and explore less-well-known states until it discovers a way to terminate earlier than 200.

  • $\begingroup$ I really really appreciate your kind help. $\endgroup$
    – Amin
    Oct 29, 2018 at 11:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.