1
$\begingroup$

MDP stands for the Markov decision process. It is a 5-length tuple used in reinforcement learning.

$$MDP = (S, A, T, R, \pi)$$

$S$ stands for a set of states, also called state space.

$A$ stands for a set of actions, also called action space.

$T$ is a probability distribution function $$T: S\times A \times S\rightarrow [0,1]$$

$R$ is a reward function

$$R: S\times A \rightarrow \mathbb{R}$$

$\pi$ is a policy function

$$\pi: S\times A \rightarrow [0,1]$$

This question is restricted to continuous spaces i.e., state and action spaces are continuous. And also to stochastic policy function. And also consider only the basic MDP instead of its flavors.

In general, MDP in reinforcement learning is applied mostly to games. And most of the games have certain start states as well as goal states.

Is there any reason for not specifying start and goal states in MDP like in a finite automaton?

Or does MDP has an implicit start and goal states (say from the values of reward function)?

Or is the MDP, by nature, defined irrespective to start and goal states? If yes, can I just imagine MDP as a state-space search problem without a particular goal?

$\endgroup$
1
$\begingroup$

Is there any reason for not specifying start and goal states in MDP like in a finite automaton?

In general MDPs have a start state distribution. That may be a single state, but does not have to be. In non-episodic problems, you might want to consider a long term state distribution under any given policy, although it is quite common to use a simple start distribution and the assumption of ergodicity for long term distribution.

In general MDPs do not have goal states. Although using the agent's actions to achieve certain desirable end states, such as winning a game or completing a puzzle, is a very common design, there is no requirement for this. The more general requirement is to maximise some aggregate of the reward at each time step - usually either a discounted sum of rewards or the mean reward.

Or does MDP has an implicit start and goal states (say from the values of reward function)?

No, although if you are designing an MDP to model some environment, and it has goal states, you will typically take the goal states into account. Likewise you will usually select the start state distribution as part of the problem definition.

Or is the MDP, by nature, defined irrespective to start and goal states?

You will need to choose at least a distribution of start states to use an MDP practically.

There is no requirement to set a goal state. Whether or not you do that depends on the problem you are modelling.

If yes, can I just imagine MDP as a state-space search problem without a particular goal?

There may or may not be a goal state. You cannot frame RL as state-space search in general. The general solution to an RL control problem is one that maximises an aggregate (sum or mean) over the rewards. There is no requirement for that reward to be received from any single state.

You can usually consider RL control methods to be policy-space searches. The value-based methods such as Q-learning perform the policy search indirectly, whilst policy gradient methods such as REINFORCE model the policy function and optimise it.

The reverse situation, if you do have a state-space search problem, for example some form of combinatorial optimisation, then you can frame it as an RL problem. However, RL would normally be a very inefficient way to perform the search, because it will perform a policy search through trial and error to find the policy which builds the desired state from a starting state. Much better AI tools exist for graph searches and combinatorial optimisations than learning the whole series of actions required to convert an arbitrary start state to a goal state through trial and error.


Aside:

$R$ is a reward function $$R: S\times A \rightarrow \mathbb{R}$$

This is not general. This looks more like an expected reward function. You can derive the Bellman equations using an expected reward function, so using the expected reward function does not interfere with most RL theory. However, individual rewards may be based on the next state, and can be stochastic, so the reward function you list does not fully define an MDP - the difference would be important when considering qualities of the MDP such as variance which will impact agent learning efficiency for example.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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