Questions tagged [optimality]
For questions about the optimality of artificial intelligence algorithms, including search or reinforcement learning algorithms.
6
questions
0
votes
1answer
70 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
39 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
31 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
325 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 ...
2
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
105 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?
