Answers.Body: <p>Your equations all look correct to me.</p>
  <p>It is <strong>not</strong> possible to solve the linear equation for state values in the vector <span class="math-container">$V$</span> without knowing the policy.</p>
  <p>There are ways of working with MDPs, through sampling of actions, state transitions and rewards, where it is possible to estimate value functions without knowing either <span class="math-container">$\pi(a|s)$</span> or <span class="math-container">$P^{a}_{ss'}$</span>. For instance, Monte Carlo policy evaluation or single-step TD learning can both do this. It is also common to work with <span class="math-container">$\pi(a|s)$</span> known but <span class="math-container">$P^{a}_{ss'}$</span> and <span class="math-container">$R^{a}_{s}$</span> unknown in model-free control algorithms such as Q learning.</p>
  <p>However, in your case, you are correct, in order to resolve the simultaneous equations you have presented, you do need to know <span class="math-container">$\pi(a|s)$</span></p>
  <p>This is not as limiting as you might think. You can construct a control method using simultaneous equations, by starting with the policy set to some arbitrary policy. Either a randomly-chosen deterministic policy or the equiprobable policy are reasonable first guesses. Then, after each solution to linear equations, you improve the policy so that each action choice maximises the expected return. This is essentially the policy iteration algorithm but replacing the policy evaluation step with the linear equations method for calculating the values.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-16T09:55:58.067Z
Answers.Text: Thanks. I understood. Also one more question I have that is, are we assuming the fact that if there exist a stochastic policy then there exist an optimal deterministic policy?
Answers.UserDisplayName: Abc1729
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-16T11:53:46.407Z
Answers.Text: @Abc1729 For a well-defined MDP with the Markov property, there will always exist one or more optimal deterministic policies. You do not require a stochastic policy for it to be optimal (but you might want one if your optimisation porcess involves exploring by sampling actions to refine estimates). There are other questions about that on this site already, but if you cannot find them or the answers on them do not help, then feel free to ask a new one
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-16T09:12:04.370Z
Answers.LastActivityDate: 2021-09-24T06:17:36.470Z
Answers.LastEditDate: 2021-09-24T06:17:36.470Z
Answers.UserDisplayName: Neil Slater
Body: <p>An MDP is a Markov Reward Process with decisions, it’s an environment in which all states are Markov. This is what we want to solve. An MDP is a tuple <span class="math-container">$(S, A, P, R, \gamma)$</span>, where <span class="math-container">$S$</span> is our state space, <span class="math-container">$A$</span> is a finite set of actions, <span class="math-container">$P$</span> is the state transition probability function,</p>
  <p><span class="math-container">$$P_{ss'}^a = \mathbb{P}[S_{t+1} = s' | S_t = s, \hspace{0.1cm}A_t = a] \label{1}\tag{1}$$</span></p>
  <p>and</p>
  <p><span class="math-container">$$R_s^a = \mathbb{E}[R_{t+1}| S_t =s, A_t = a]$$</span></p>
  <p>and a discount factor <span class="math-container">$\gamma$</span>.</p>
  <p>This can be seen as a linear equation in <span class="math-container">$|S|$</span> unknowns, which is given by,</p>
  <p><span class="math-container">$$V = R + \gamma PV  \hspace{1mm}  \label{2}\tag{2}$$</span></p>
  <p><span class="math-container">$V$</span> is value of a state vector, <span class="math-container">$R$</span> is immediate reward vector, <span class="math-container">$P$</span> is transition probability matrix, where each element at <span class="math-container">$(i,j)$</span> in <span class="math-container">$P$</span> is given by,  <span class="math-container">$ P[i][j] = P(i \mid j)$</span> i.e., probability that I am in state <span class="math-container">$j$</span> going to state <span class="math-container">$i$</span>.</p>
  <p>As <span class="math-container">$P$</span> is given, we treat, equation <span class="math-container">$\ref{2}$</span> as a linear equation in <span class="math-container">$V$</span>.
  But <span class="math-container">$P[i][j] = \sum_a (\pi(a \mid j) \times \mathrm{p}(i \mid j, a) )$</span>. But, <span class="math-container">$ \pi (a \mid s)$</span> (i.e., probability that I will take action a in state s) is NOT given.</p>
  <p><em>So, how can we frame this problem as the solution to a system of linear equations in \ref{2}, if we only know <span class="math-container">$ P^a_{ss'}$</span> and we do <strong>not</strong> know <span class="math-container">$ \pi(a \mid s)$</span>, which is needed to calculate <span class="math-container">$P[i][j]$</span>?</em></p>
  
Tags: <markov-decision-process><policies><bellman-equations><transition-model>
Title: How can we find the value function by solving a system of linear equations without knowing the policy?
UserDisplayName: Abc1729
ThreadText: # How can we find the value function by solving a system of linear equations without knowing the policy?
  
  (Asked by: username_0 on 2021-02-16)
  
  An MDP is a Markov Reward Process with decisions, it’s an environment in which all states are Markov. This is what we want to solve. An MDP is a tuple $(S, A, P, R, \gamma)$, where $S$ is our state space, $A$ is a finite set of actions, $P$ is the state transition probability function,
  
  $$P\_{ss'}^a = \mathbb{P}[S\_{t+1} = s' | S\_t = s, \hspace{0.1cm}A\_t = a] \label{1}\tag{1}$$
  
  and
  
  $$R\_s^a = \mathbb{E}[R\_{t+1}| S\_t =s, A\_t = a]$$
  
  and a discount factor $\gamma$.
  
  This can be seen as a linear equation in $|S|$ unknowns, which is given by,
  
  $$V = R + \gamma PV \hspace{1mm} \label{2}\tag{2}$$
  
  $V$ is value of a state vector, $R$ is immediate reward vector, $P$ is transition probability matrix, where each element at $(i,j)$ in $P$ is given by, $ P[i][j] = P(i \mid j)$ i.e., probability that I am in state $j$ going to state $i$.
  
  As $P$ is given, we treat, equation $\ref{2}$ as a linear equation in $V$.
  But $P[i][j] = \sum\_a (\pi(a \mid j) \times \mathrm{p}(i \mid j, a) )$. But, $ \pi (a \mid s)$ (i.e., probability that I will take action a in state s) is NOT given.
  
  *So, how can we frame this problem as the solution to a system of linear equations in \ref{2}, if we only know $ P^a\_{ss'}$ and we do **not** know $ \pi(a \mid s)$, which is needed to calculate $P[i][j]$?*
  
  **Tags:** markov-decision-process, policies, bellman-equations, transition-model
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2021-02-16. Score: 3 | Accepted answer
  
  Your equations all look correct to me.
  
  It is **not** possible to solve the linear equation for state values in the vector $V$ without knowing the policy.
  
  There are ways of working with MDPs, through sampling of actions, state transitions and rewards, where it is possible to estimate value functions without knowing either $\pi(a|s)$ or $P^{a}\_{ss'}$. For instance, Monte Carlo policy evaluation or single-step TD learning can both do this. It is also common to work with $\pi(a|s)$ known but $P^{a}\_{ss'}$ and $R^{a}\_{s}$ unknown in model-free control algorithms such as Q learning.
  
  However, in your case, you are correct, in order to resolve the simultaneous equations you have presented, you do need to know $\pi(a|s)$
  
  This is not as limiting as you might think. You can construct a control method using simultaneous equations, by starting with the policy set to some arbitrary policy. Either a randomly-chosen deterministic policy or the equiprobable policy are reasonable first guesses. Then, after each solution to linear equations, you improve the policy so that each action choice maximises the expected return. This is essentially the policy iteration algorithm but replacing the policy evaluation step with the linear equations method for calculating the values.
  
  > **Comments:**
  > **username_0**: Thanks. I understood. Also one more question I have that is, are we assuming the fact that if there exist a stochastic policy then there exist an optimal deterministic policy?  
  > **username_1**: @username_0 For a well-defined MDP with the Markov property, there will always exist one or more optimal deterministic policies. You do not require a stochastic policy for it to be optimal (but you might want one if your optimisation porcess involves exploring by sampling actions to refine estimates). There are other questions about that on this site already, but if you cannot find them or the answers on them do not help, then feel free to ask a new one  
  
  ---
  
  