Questions tagged [optimality]
For questions about the optimality of artificial intelligence algorithms, including search or reinforcement learning algorithms.
7
questions
0
votes
1answer
62 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 ...
0
votes
1answer
83 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?
3
votes
1answer
52 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 \...
1
vote
0answers
41 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 ...
5
votes
2answers
348 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 ...
3
votes
2answers
1k 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?
1
vote
2answers
142 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?
