Answers.Body: <blockquote>
  <p>Is there any reason for not specifying start and goal states in MDP like in a finite automaton?</p>
  </blockquote>
  <p>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 <a href="https://en.wikipedia.org/wiki/Ergodicity" rel="nofollow noreferrer">ergodicity</a> for long term distribution.</p>
  <p>In general MDPs do <strong>not</strong> 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.</p>
  <blockquote>
  <p>Or does MDP has an implicit start and goal states (say from the values of reward function)?</p>
  </blockquote>
  <p>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.</p>
  <blockquote>
  <p>Or is the MDP, by nature, defined irrespective to start and goal states?</p>
  </blockquote>
  <p>You will need to choose at least a distribution of start states to use an MDP practically.</p>
  <p>There is no requirement to set a goal state. Whether or not you do that depends on the problem you are modelling.</p>
  <blockquote>
  <p>If yes, can I just imagine MDP as a state-space search problem without a particular goal?</p>
  </blockquote>
  <p>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.</p>
  <p>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.</p>
  <p>The reverse situation, if you do have a state-space search problem, for example some form of combinatorial optimisation, then you <em>can</em> 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.</p>
  <hr />
  <p>Aside:</p>
  <blockquote>
  <p><span class="math-container">$R$</span> is a reward function
  <span class="math-container">$$R: S\times A  \rightarrow \mathbb{R}$$</span></p>
  </blockquote>
  <p>This is not general. This looks more like an <strong>expected</strong> 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, <em>and</em> 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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-08-09T09:00:14.417Z
Answers.LastActivityDate: 2021-08-09T09:06:51.257Z
Answers.LastEditDate: 2021-08-09T09:06:51.257Z
Answers.UserDisplayName: Neil Slater
Body: <p>MDP stands for the Markov decision process. It is a 5-length tuple used in reinforcement learning.</p>
  <p><span class="math-container">$$MDP = (S, A, T, R, \pi)$$</span></p>
  <p><span class="math-container">$S$</span> stands for a set of states, also called state space.</p>
  <p><span class="math-container">$A$</span> stands for a set of actions, also called action space.</p>
  <p><span class="math-container">$T$</span> is a probability distribution function  <span class="math-container">$$T: S\times A \times S\rightarrow [0,1]$$</span></p>
  <p><span class="math-container">$R$</span> is a reward function</p>
  <p><span class="math-container">$$R: S\times A  \rightarrow \mathbb{R}$$</span></p>
  <p><span class="math-container">$\pi$</span> is a policy function</p>
  <p><span class="math-container">$$\pi: S\times A  \rightarrow [0,1]$$</span></p>
  <p>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.</p>
  <p>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.</p>
  <p>Is there any reason for not specifying start and goal states in MDP like in a finite automaton?</p>
  <p>Or does MDP has an implicit start and goal states (say from the values of reward function)?</p>
  <p>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?</p>
  
Tags: <reinforcement-learning><markov-decision-process><state-spaces>
Title: Is there any inherent assumption of start and goal states in an MDP?
UserDisplayName: hanugm
ThreadText: # Is there any inherent assumption of start and goal states in an MDP?
  
  (Asked by: username_0 on 2021-08-09)
  
  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?
  
  **Tags:** reinforcement-learning, markov-decision-process, state-spaces
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2021-08-09. Score: 1
  
  > 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](https://en.wikipedia.org/wiki/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.
  
  
  ---
  
  