5 votes
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 ...
mikkola's user avatar
  • 580
3 votes
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 ...
nbro's user avatar
  • 40.1k
3 votes
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 ...
harwiltz's user avatar
  • 1,126
3 votes
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 ...
Aadit M Shah's user avatar
2 votes
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 ...
nbro's user avatar
  • 40.1k
2 votes
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 ...
David's user avatar
  • 4,760
2 votes
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 ...
nbro's user avatar
  • 40.1k
2 votes

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 ...
Neil Slater's user avatar
  • 31.5k
2 votes
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 ...
nbro's user avatar
  • 40.1k
2 votes

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 ...
nbro's user avatar
  • 40.1k
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 ...
Alberto's user avatar
  • 1,667
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 ...
respectful's user avatar
  • 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 ...
Neil Slater's user avatar
  • 31.5k
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 ...
Oliver Mason's user avatar
  • 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 ...
D.W.'s user avatar
  • 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 ...
mikkola's user avatar
  • 580
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 ...
Arnaldur's user avatar
  • 161

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