# Tag Info

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

6

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

5

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

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

4

$\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) \... 4 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 ... 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 ... 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 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 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 deterministic 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,$\...

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 The$\epsilon$-greedy policy is a policy that chooses the best action (i.e. the action associated with the highest value) with probability$1-\epsilon \in [0, 1]$and a random action with probability$\epsilon $. The problem with$\epsilon$-greedy is that, when it chooses the random actions (i.e. with probability$\epsilon$), it chooses them uniformly (i.e. ... 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 ... 1 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 ... 1 I think most of it is correct. Q function(also called state-action value, or just action value): How good it is to be in a state S and perform action A while following policy π. It uses reward to measure the state-action value This is a bit off. Q function basically tells you how good it is to be in state S and perform action A, and follow policy$\pi$... 1 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 ... 1 The formula in question uses a function N(state, action) that defines a visit count of a state-action pair (introduced on page 3). To describe how it is used, lets first describe the steps of AlphaGo Zero as a whole. There are 4 "phases" to the Monte-Carlo tree search in AlphaGo Zero as depicted in Figure 2. The first 3 expand and update the tree and ... 1 You can simply train a policy from the inputs to predict the actions in your dataset. You can use the cross entropy loss for this, i.e. maximize the the log probability that the policy assigns to the actions in the data set when given the corresponding inputs. This is called behavioral cloning. The result is an approximation of the behavioral policy that ... 1 Both value iteration (VI) and policy iteration (PI) algorithms are guaranteed to converge to the optimal policy, so it is expected that you get similar policies from both algorithms (if they have converged). However, they do this differently. VI can be seen as truncated version of PI. Let me first illustrate the pseudocode of both algorithms (taken from ... 1 If a policy is fixed, it is said that an MDP becomes an MRP. I would change the phrasing slightly here, to: If a policy is fixed, an MDP can be accurately modeled as an MRP. Why is this so? Aren't the transitions and rewards still parameterized by the action and current state? In other words, aren't the transition and reward matrices still cubes? The ... 1 Bias is not necessarily bad, even though the term bias usually has a negative connotation. In fact, in machine learning, inductive bias is quite important and necessary. For example, if you want to learn a function$f(x) = y$, where$x \in \mathcal{X}$and$y \in \mathcal{Y}$, you often just have a finite dataset$\mathcal{D} = \{ (x_i, y_i)\}_{i=1}^N$, ... 1 Having low variance is important in general as it reduces the number of samples needed to obtain accurate estimates. This is the case for all statistical machine learning, not just reinforcement learning. In general, if you are estimating a mean or expected quantity by taking many samples, the variation in the error is proportional to$\frac{\sigma}{\sqrt{N}...

1

If your game agent performs any kind of advance learning from self play or database of moves, that will generate parameters for some kind of model (e.g. a table of expected values, or neural network weights to select a preferred action). This is unavoidable, and if you want to re-use the results of that machine learning, you absolutely have to store the ...

1

Why are they comparing state value function to action value function? It is because $v_{\pi}(s)$ and $q_{\pi}(s,a)$ measure the same quantity at different stages of the trajectory. By comparing the values at the same $s$ and modifying how $a$ is selected, the proof makes assertions about how that choice impacts the value. It is important to recall that \$v_{...

1

I think you're overthinking it. I've never seen a formalisation of the concept of "stationary policy" (apart from yours). However, in general, "stationary" means that something does not change (over time). In the context of reinforcement learning, you can interpret it in such a way that it is consistent with the context where you find this expression, unless ...

1

If you simulate many trajectories and receive many estimates of the two returns you're interested in, you could empirically compare their sample variances. However, the variance of ordinary importance sampling is in general unbounded. If you're wanting some theoretical bounds on the variance of importance sampling estimates, I'd start with weighted ...

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