People who code: we want your input. Take the Survey
6

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 selection is not based on what happened before (so you are not trying to model your opponent, or trick them into believing you will always play scissors and then ...


3

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 MDP is to find a policy that maximizes expected returns. Suppose you're in state $s$. According to your action-value function, let's say actions $a$ maximizes ...


3

Your calculations are correct, but you have misinterpreted the equations and the diagram. The index $k$ in $v_k$ for the diagram refers to the policy evaluation update iteration only, and is not related to the policy update step (which uses the notation $\pi'$ and does not mention $k$). Policy improvement consists of multiple sweeps through states to fully ...


2

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-right corner, which is a terminal state. We'll name the four cells $NW$, $NE$, $SW$ and $SE$ (for north-west, north-east, south-west and south-east). We'll ...


2

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 policy for a given value function: this only happens when two actions have the same value in a given state. Nevertheless, both policies lead to the same ...


2

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 optimal policy. This can be seen using the equation for optimal deterministic policy in terms of optimal value function: $$\pi^*(s) = \text{argmax}_a [\sum_{r,s'}p(r,...


2

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 the transition dynamics of the MDP. Now, as you pointed out the optimal value function is defined as $v_*(s) = \max_\pi v_\pi(s)\; ; \;\forall s \in \mathcal{S}$....


1

In general they are not the same and that should be clear as to why -- mathematically you are conditioning on an extra random variable being known in the state-action value function. You have the correct relationship between them, but I think your understanding of the two may be slightly off. The state-action value function is a function of both $s$ and $a$ ...


1

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 policy can be misleading, as there may be many different optimal policies. For example, certainly we could imagine an MDP where $Q^*(s,a_0) = Q^*(s,a_1)$ for two ...


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