Questions tagged [optimality]

For questions about the optimality of AI algorithms and solutions.

Filter by
Sorted by
Tagged with
0 votes
1 answer
52 views

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

I am quite new to RL. I would like to know why a state-dependent reward function R(s) is more restrictive than a state-action-dependent reward function R(s, a)? And why is it that a policy can be ...
TicTacToemat's user avatar
0 votes
1 answer
351 views

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

The book "Artificial Intelligence: A Modern Approach" (4th edition, global version) says "With an admissible heuristic, A* is cost-optimal...". An admissible heuristic is one ...
numq's user avatar
  • 1
1 vote
1 answer
78 views

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

By substituting the optimal policy $\pi_{\star}$ into the Bellman equation, we get the Bellman equation for $v_{\pi_{\star}}(s)=v_{\star}(s)$: $$ v_{\star}(s) = \sum\limits_a \pi_{\star}(a|s) \sum\...
DSPinfinity's user avatar
0 votes
1 answer
229 views

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

I am trying to solve the following exercise from Sutton and Barto: Sutton and Barto Exercise 3.27 Give an equation for $\pi_*$ in terms of $q_*(s,a)$ However, I am struggling to do so. I know that $\...
user's user avatar
  • 145
3 votes
1 answer
291 views

Can we achieve optimality with minimax using an evaluation function?

The following quote (from AIMA) refers to the situation in which the minimax algorithm computes its values directly from the terminal states. (The) definition of optimal play for MAX assumes that MIN ...
Kestina's user avatar
  • 31
3 votes
1 answer
181 views

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

In "AI: A Modern Approach", 4th edition, by Russell and Norvig, they give a purported proof that A* is cost-optimal for any admissible heuristic. The given proof seems most certainly wrong. ...
vdbuss's user avatar
  • 81
1 vote
1 answer
643 views

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

Let $M$ be an MDP with two states, $A$ and $B$, where $A$ is the starting state, and you always transit to the final state $B$ using two possible actions. $A_1$ gives you rewards that are normally ...
Abc1729's user avatar
  • 45
0 votes
1 answer
919 views

Are hill climbing variations always optimal and complete?

Are hill climbing variations (like steepest ascent hill climbing, stochastic hill climbing, random restart hill climbing, local beam search) always optimal and complete?
user avatar
3 votes
1 answer
110 views

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

I am reading Sutton & Bartos's Book "Introduction to reinforcement learning". In this book, the defined the optimal value function as: $$v_*(s) = \max_{\pi} v_\pi(s),$$ for all $s \in \...
Tamar's user avatar
  • 33
1 vote
0 answers
97 views

Minimax algorithm with only partial visibility

I'm trying to implement the minimax algorithm with alpha beta pruning on a game that works like this: Player 1 plays (x1, y1). Player 2 can only see the x-value (x1) that Player 1 played (and not ...
SpiderManCity's user avatar
5 votes
2 answers
991 views

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

If there are two different optimal policies $\pi_1, \pi_2$ in a reinforcement learning task, will the linear combination (or affine combination) of the two policies $\alpha \pi_1 + \beta \pi_2, \alpha ...
yang liu's user avatar
3 votes
2 answers
3k views

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

If uniform cost search is used for both the forward and backward search in bidirectional search, is it guaranteed the solution is optimal?
user avatar
1 vote
2 answers
636 views

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

Could someone please help me gain some intuition as to why the optimal policy for a Markov Decision Process in the infinite horizon case (agent acts forever) is deterministic?
stoic-santiago's user avatar
3 votes
2 answers
4k views

How to make minimax optimal?

By optimal I mean that: If max has a winning strategy then minimax will return the strategy for max with the fewest number of moves to win. If min has a winning strategy then minimax will return the ...
Aadit M Shah's user avatar