# Tag Info

4

I think the result you are referring to is the one that says that there always exists a deterministic optimal policy for an MDP. This is true. But note that this does not imply that a stochastic optimal policy can not exist at the same time. Suppose you have an MDP with one state and two actions $a_1$ and $a_2$, both yielding the reward 0 in expectation (as ...

3

Suppose you learned your action-value function perfectly. Recall that the action-value function measures the expected return after taking a given action in a given state. Now, the goal when solving an MDP is to find a policy that maximizes expected returns. Suppose you're in state $s$. According to your action-value function, let's say actions $a$ maximizes ...

2

The value function is defined as $v_\pi(s) = \mathbb{E}_\pi[G_t | S_t = s]$ where $G_t$ are the (discounted) returns from time step $t$. The expectation is taken with respect to the policy $\pi$ and the transition dynamics of the MDP. Now, as you pointed out the optimal value function is defined as $v_*(s) = \max_\pi v_\pi(s)\; ; \;\forall s \in \mathcal{S}$....

2

Short answer Two policies are different if they take different actions in a specific state $s$ (or they give different probabilities of taking those actions in $s$). There can be more than one optimal policy for a given value function: this only happens when two actions have the same value in a given state. Nevertheless, both policies lead to the same ...

2

Yes, in general any linear combination of probability distributions between optimal policies is also an optimal policy. In fact any combination with each state treated separately will also be an optimal policy. This can be seen using the equation for optimal deterministic policy in terms of optimal value function: \pi^*(s) = \text{argmax}_a [\sum_{r,s'}p(r,...

2

UCS is optimal (but not necessarily complete) Let's first recall that the uniform-cost search (UCS) is optimal (i.e. if it finds a solution, which is not guaranteed unless the costs on the edges are big enough, that solution is optimal) and it expands nodes with the smallest value of the evaluation function $f(n) = g(n)$, where $g(n)$ is the length/cost of ...

1

No, they are prone to get stuck in local maxima, unless the whole search space is investigated. A simple algorithm will only ever move upwards; if you imagine you're in a mountain range, this will not get you very far, as you will need to go down before going up higher. You can see that going down a bit will have a net benefit, but the search algorithm will ...

1

The premise of this question is somewhat misleading. There is a deterministic optimal policy for a MDP, but this does not mean a stochastic optimal policy never exists. Talking about the optimal policy can be misleading, as there may be many different optimal policies. For example, certainly we could imagine an MDP where $Q^*(s,a_0) = Q^*(s,a_1)$ for two ...

1

It depends on the stopping condition. If the stopping condition is "stop as soon as any vertex is encountered by both the forward and backward scan", then bidirectional uniform-cost search is not a correct algorithm -- it is not guaranteed to output the optimal path. But it is possible to adjust the stopping condition to make bidirectional ...

Only top voted, non community-wiki answers of a minimum length are eligible