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
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?