8

A deterministic policy is a function of the form $\pi_{\mathbb{d}}: S \rightarrow A$, that is, a function from the set of states of the environment, $S$, to the set of actions, $A$. The subscript $_{\mathbb{d}}$ only indicates that this is a ${\mathbb{d}}$eterministic policy. For example, in a grid world, the set of states of the environment, $S$, is ...


8

A stationary policy is a policy that does not change. Although strictly that is a time-dependent issue, that is not what the distinction refers to in reinforcement learning. It generally means that the policy is not being updated by a learning algorithm. If you are working with a stationary policy in reinforcement learning (RL), typically that is because ...


8

Is the optimal policy always stochastic (that is, a map from states to a probability distribution over actions) if the environment is also stochastic? No. An optimal policy is generally deterministic unless: Important state information is missing (a POMDP). For example, in a map where the agent is not allowed to know its exact location or remember ...


7

The MDP defines the environment (which corresponds to the task that you need to solve), so it defines e.g. the states of the environment, the actions that you can take in those states, the probabilities of transitioning from one state to the other and the probabilities of getting a reward when you take a certain action in a certain state. The policy ...


5

I would say no. For example, consider the multi-armed bandit problem. So, you have $n$ arms which all have a probability of giving you a reward (1 point, for example), $p_i$, $i$ being between 1 and $n$. This is a simple stochastic environment: this is a one state environment, but it is still an environment. But obviously the optimal policy is to choose ...


5

Given that policies are probability distributions, in principle, you can use any metric or measure of distance that can be used to compare two probability distributions. (Note that notions of distance are not necessarily metrics in a mathematical sense). A common measure is the Kullback–Leibler divergence (which is not a metric, in a mathematical sense, ...


4

for example, the "greedy policy" always chooses the action with the highest expected return, no matter which state we are in The "no matter which state we are in" there is generally not true; in general, the expected return depends on the state we are in and the action we choose, not just the action. In general, I wouldn't say that a policy is a mapping ...


3

$\pi(s)$ does not mean $q(s,a)$ here. $\pi(s)$ is a policy that represents probability distribution over action space for a specific state. $q(s,a)$ is a state-action pair value function that tells us how much reward do we expect to get by taking action $a$ in state $s$ onwards. For the value iteration on the right side with this update formula: $v(s) \...


3

A stationary policy, $\pi_t$, is a policy that does not change over time, that is, $\pi_t = \pi, \forall t \geq 0$, where $\pi$ can either be a function, $\pi: S \rightarrow A$ (a deterministic policy), or a conditional density, $\pi(A \mid S)$ (a stochastic policy). A non-stationary policy is a policy that is not stationary. More precisely, $\pi_i$ may not ...


3

In the book, the phrase "generate the data" refers to the data from observations about states, actions, next states and rewards, that then get used to make value estimate updates. In both the SARSA and Q learning pseudocode from the book, there is a behaviour policy that selects the next action to take. Other than the initial start state, this ...


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

You appear to comparing the value table update steps in policy iteration and value iteration, which are both derived from Bellman equations. Policy iteration In policy iteration, a policy lookup table is generated, which can be arbitrary. It usually maps a deterministic policy $\pi(s): \mathcal{S} \rightarrow \mathcal{A}$, but can also be of the form $\pi(a|...


3

A Q table allows you to look up any state/action pair in it and find the associated action value. It is not itself a policy. However, in order to calculate the action values, you will have assumed something about the policy. The most common policy scenarios with Q learning are that it will converge on (learn) the values associated with a given target policy, ...


3

Your equations all look correct to me. It is not possible to solve the linear equation for state values in the vector $V$ without knowing the policy. There are ways of working with MDPs, through sampling of actions, state transitions and rewards, where it is possible to estimate value functions without knowing either $\pi(a|s)$ or $P^{a}_{ss'}$. For instance,...


2

I guess I'm having difficulty grasping the concept that the goodness of a state changes depending on how an agent got there It doesn't. The value of a state changes depending on what the agent will do next. That is where the dependency on the policy comes in, not in past behaviour, but expectations of future behaviour. The future behaviour depends on the ...


2

A stationary policy is the one that does not depend on time. Meaning that the agent will take the same decision whenever certain conditions are met. This stationary policy may be probabilistic which implies that the probability of choosing an action remains the same. It may take different decisions but the probability remains the same. A Stationary ...


2

You are right: a stationary policy is independent of time. It is basically a mapping from states to actions (or probability distributions over actions). Regardless of the point in time in which the agent observes the state $s$ it will select an action $a$ (or select a probability $\pi(a \vert s)$ for every action $a$).


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

So, here's is the question: Is it true that a non-stationary policy must satisfy this condition? $$ \forall i, j \in \mathbb{N}, s \in S, \pi (i, s) = \pi(j, s) $$ With your custom notation (which certainly isn't common, but seems reasonable)... I assume you meant to say that a stationary policy must satisfy that condition, rather than that a non-...


2

The output layer of the network contains one unit, telling me the Q value of the provided state with the assumption that the action taken in that state will be determined by the policy. Typically in Reinforcement Learning, the symbol $Q$ is used when you calculate an action value, and if you are evaluating for a specific policy, it is noted $q_{\pi}(s,a)$ ...


2

The good news is that: Your MDP appears valid, with well-defined states, actions. It has state transition and reward functions (which you have implemented as matrices). There is nothing else to add, it's a full MDP. You could use this MDP to evaluate a policy, using a variety of reinforcement learning (RL) methods suitable for finite discrete MDPS. For ...


2

First of all, $Q_\pi(s, a)$ IS DEFINED AS the value (i.e. the expected return) of taking some action $a$ in some state $s$, AND THEN following some given policy $\pi$ (until e.g. the end of the game or your life). In other words, suppose that you take action $a$ in state $s$, AND THEN use the policy $\pi$ to behave in the world until you die, then $Q_\pi(s, ...


2

Why do RL implementations converge on one action? If the optimal policy shouldn't always select the same action in the same state, i.e., if the optimal policy isn't deterministic (e.g., in the case of the rock paper scissors, the optimal policy cannot be deterministic because any intelligent player would easily memorize your deterministic policy, so, after ...


2

Aside from the points raised in nbro's answer, I'd like to point out that for a single MDP (a single instance of a "problem"), it may be sensible to study it from perspectives that include no policy at all, or multiple different policies. For instance, if I have an MDP, I may be interested in studying it by looking at various inherent properties of the ...


2

It seems to me that you're thinking about the parameters a and b as being characteristic of the agent that's moving in the environment (therefore determining the final policy), but they are actually a characteristic of the environment. Think of a frozen lake. You want to pass the lake but there is a hole five meters in front of you. Let's say you have boots ...


2

Value function: How good it is to be in a state $s$ following policy $\pi$. There are different value functions. There's the state value function, often denoted as $v(s)$ (or $V(s)$), so it's a function of only one variable, i.e. $s$ (a state). There's the state-action value function $q(s, a)$ (or $Q(s, a$)). A value function is a function, so it's not a ...


2

Your policy gradient algorithms appear to be working as intended. All standard MDPs have one or more deterministic optimal solutions, and those are the policies that solvers will converge to. Making any of these policies more random will often reduce their effectiveness, making them sub-optimal. So once consistently good actions are discovered, the learning ...


2

In the PDF of the original paper for UCB1 you linked, in page 242-243 the authors proves why non-optimal machines get played much less (in fact, logarithmically less) than the optimal ones. $c$ decides whether they indeed would, and $c=\sqrt{2}$ is the minimum choice of $c$. We want to show that the number of runs for non-optimal machines ($n_i$, for non-...


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

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


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