# Policy dependent on initial state distribution in finite horizon MDPs

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?

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.