Consider an MDP defined as the tuple $\langle S,A,R,P,\mu,\lambda\rangle$ where $S$ is the state space, $A$ the action space, $R:S\times A\times S\to\mathbb{R}$ the reward function, $P$ the transition probabilities, $\mu$ the initial state distribution, and $\lambda$ is the discount factor.

Let the decision horizon be finite. The expected discounted return under a given policy $\pi = (\pi_1,\ldots,\pi_{T-1})$, where each $\pi_t:S\to A$, is defined as \begin{align*} F(\pi,\mu) = E_{\pi,\mu}\big[\sum_{t=1}^{T-1}\lambda^tR(s_t,a_t,s_{t+1}) + \lambda^TR(s_{T-1},s_T)\mid s_1\sim \mu\big] \end{align*} where $a_t = \pi_t(s_t)$ and the expectation is taken with respect to the probability distribution on the states induced by the initial state distribution $\mu$ and the policy $\pi$. An optimal policy is defined as $\pi^*\in\arg \max_\pi F(\pi,\mu)$.

It seems to me that the math says that since we are only maximizing over $\pi$, there is still a residual dependence of the optimal policy on $\mu$, i.e., mathematically it should be written: $\pi_{\mu}^*\in\arg \max_\pi F(\pi,\mu)$.

Question: Are optimal policies in MDPs dependent upon the initial state distribution? If not, what conditions allow us to rule out this dependence?

  • $\begingroup$ I just would like to note that there's also Artificial Intelligence SE, where there are a lot of RL enthusiasts. $\endgroup$ – nbro Sep 15 '20 at 10:56

On an MDP the main assumption is that states are independent (Markov Decision Process). Any policy in such environments will decide an action on a given state independently of previous visited states, taken actions and received rewards.

This means that the optimal policy doesn't depend at all on the initial distribution. However the initial distribution might affect the expected reward but it won't affect the optimal policy.

To be clear on your second question, the condition that allow us to rule out this dependency is the markov property: The future is independent from the past given the current state. So the optimal policy will have a distribution of actions to take depending only in the state, without caring about the weight of such state in the initial distribution.


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.