# Tag Info

## Hot answers tagged optimality

Accepted

### Are optimal policies always deterministic, or can there also be optimal policies that are stochastic?

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 ...
• 579
Accepted

### How are these two equations for the optimal state-value function equivalent?

Your first equation is the definition of any state value function, so it must also be definition of the optimal state value function $v_*$. The second equation is the definition of $v_*$ in terms of ...
• 40.9k
Accepted

### Why is the optimal policy for an infinite horizon MDP deterministic?

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 ...
• 1,136
Accepted

### How to make minimax optimal?

Minimax deals with two kinds of values: Estimated values determined by a heuristic function. Actual values determined by a terminal state. Commonly, we use the following denotational semantics for ...

### Is there an error in A* optimality proof Russel-Norvig 4th edition?

You did not compute $g(n)$ correctly. A* expands according to the evaluation function $f(n) = g(n) + h(n)$, where $g(n)$ is the cost of the path from the start node to $n$. Initially, you add $A$ to ...
• 40.9k
Accepted

### If uniform cost search is used for bidirectional search, is it guaranteed the solution is optimal?

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 ...
• 40.9k
Accepted

### How is $v_*(s) = \max_{\pi} v_\pi(s)$ also applicable in the case of stochastic policies?

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 ...
• 4,920
Accepted

### Given two optimal policies, is an affine combination of them also optimal?

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 ...
• 40.9k

### Given two optimal policies, is an affine combination of them also optimal?

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 ...
• 32.7k
Accepted

### What is the equation for $\pi_*$ in terms of $q_*(s,a)$?

An optimal policy is just a greedy policy with respect to the optimal state-action value function (which is unique for a given MDP). So, $\pi_* = \text{argmax}_a q_*(s,a)$ is almost correct - it ...
• 40.9k
Accepted

### Why is the better policy defined with respect to all the states values being greater?

No, the answer of @foreverska is wrong, otherwise they would have said “better givena specific $\mu(s)$”. The reason is simply that given 2 policies, where one performs better than the other only in a ...
• 2,293
1 vote

### Why is the better policy defined with respect to all the states values being greater?

If the subsequent policy is better in 99 out of 100 states this would seem to be better. But imagine if the next policy in the iteration is also better in 99 out of 100 states but the one state is a ...
• 1,298
1 vote

### Why is R(s) more restrictive than R(s, a) in an MDP?

you have in front of you 10 slot machines you can play with any of them, and each of them have a specific winrate (reward function) the only state of this MDP is the initial state, the one where you ...
• 2,293
1 vote

### Can A* be non-optimal if it uses an admissible but inconsistent heuristic with graph search?

TL;DR: All A* requires to find the optimal path is an admissible heuristic I'll read that section of the book for more clarity and extend this answer; though, I believe the way to interpret that ...
• 1,106
1 vote

### Can we achieve optimality with minimax using an evaluation function?

You can take any two player zero-sum game and change its rules, so that they become: Start from the game state being evaluated. Play for up to N turns. If no winner is found after N turns, the winner ...
• 32.7k
1 vote
Accepted

### Are hill climbing variations always optimal and complete?

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 ...
• 5,397
1 vote

### If uniform cost search is used for bidirectional search, is it guaranteed the solution is optimal?

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 ...
• 307
1 vote

### Why is the optimal policy for an infinite horizon MDP deterministic?

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 ...
• 579
1 vote

### How to make minimax optimal?

Short version below. When implementing a minimax algorithm the purpose is usually to find the best possible position of a game board for the player you call max after some amount of moves. In some ...
• 161

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