Questions tagged [optimality]

For questions about the optimality of artificial intelligence algorithms, including search or reinforcement learning algorithms.

Filter by
Sorted by
Tagged with
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?