6 votes
Accepted

What's the optimal policy in the rock-paper-scissors game?

For this, we will need game theory. In game theory, an optimal strategy is one that cannot be exploited by the opponent even if they know your strategy. Let's say you want a strategy where your move ...
Robby Goetschalckx's user avatar
5 votes
Accepted

What is the difference between a greedy policy and an optimal policy?

I would like to know if the optimal value function can also be defined as $$v_*(s_t) = \max_{a \in A(s_t)} \big\{ E_F \left[ r_{t+1} | s_t,a \right]+ \delta E_F \left[v_* \left(s_{t+1}\right)| s_t,a \...
Neil Slater's user avatar
  • 31.5k
3 votes
Accepted

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

Suppose you learned your action-value function perfectly. Recall that the action-value function measures the expected return after taking a given action in a given state. Now, the goal when solving an ...
harwiltz's user avatar
  • 1,126
2 votes
Accepted

What does $v(S_{t+1})$ mean in the optimal state-action value function?

I am not sure if it is standard notation, but Sutton & Barto use a convention that a function of a random variable is a new random variable that maps between values of the old variable to values ...
Neil Slater's user avatar
  • 31.5k
2 votes
Accepted

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

The value function is defined as $v_\pi(s) = \mathbb{E}_\pi[G_t | S_t = s]$ where $G_t$ are the (discounted) returns from time step $t$. The expectation is taken with respect to the policy $\pi$ and ...
David's user avatar
  • 4,760
2 votes
Accepted

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

Short answer Two policies are different if they take different actions in a specific state $s$ (or they give different probabilities of taking those actions in $s$). There can be more than one optimal ...
nbro's user avatar
  • 40.2k
2 votes

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

Yes, in general any linear combination of probability distributions between optimal policies is also an optimal policy. In fact any combination with each state treated separately will also be an ...
Neil Slater's user avatar
  • 31.5k
2 votes
Accepted

An example of a unique value function which is associated with multiple optimal policies

Consider a very simple grid-world, consisting of 4 cells, where an agent starts in the bottom-left corner, has actions to move North/East/South/West, and receives a reward $R = 1$ for reaching the top-...
Dennis Soemers's user avatar
  • 10.2k
1 vote
Accepted

In which community does using a Bayesian regression model as a reward function with exploration vs. exploitation challenges fall under?

One community that has very recently been attacking problems of the type posed by your question is the Bayesian sequential optimal experimental design (Bayesian sOED) community. The Bayesian sOED ...
DeepQZero's user avatar
  • 1,387
1 vote
Accepted

How is policy iteration capable of improving on a deterministic policy?

These statements are not true for policy iteration and dynamic programming: Since the policy is stochastic and the initial state is the same, we'll always take the same path and evaluate the same ...
Neil Slater's user avatar
  • 31.5k
1 vote
Accepted

Can an optimal policy have a value function that has a smaller value for a state than a non-optimal policy?

Can't it be that the optimal policy thinks a state isn't that good and gives him a low value but perform best in comparison with other policies which have higher values for this state? No, this is ...
Neil Slater's user avatar
  • 31.5k
1 vote

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

The premise of this question is somewhat misleading. There is a deterministic optimal policy for a MDP, but this does not mean a stochastic optimal policy never exists. Talking about the optimal ...
mikkola's user avatar
  • 580

Only top scored, non community-wiki answers of a minimum length are eligible