# Tag Info

Accepted

### What is the difference between First-Visit Monte-Carlo and Every-Visit Monte-Carlo Policy Evaluation?

The first-visit and the every-visit Monte-Carlo (MC) algorithms are both used to solve the prediction problem (or, also called, "evaluation problem"), that is, the problem of estimating the value ...
Accepted

### How does "Monte-Carlo search" work?

Monte Carlo method is an approach where you generate a large number of random values or simulations and form some sort of conlusions based on the general patterns, such as the means and variances. As ...

### Why do we need importance sampling?

Importance sampling is typically used when the distribution of interest is difficult to sample from - e.g. it could be computationally expensive to draw samples from the distribution - or when the ...
Accepted

### What does the term $|\mathcal{A}(s)|$ mean in the $\epsilon$-greedy policy?

This expression: $|\mathcal{A}(s)|$ means $|\quad|$ the size of $\mathcal{A}(s)$ the set of actions in state $s$ or more simply the number of actions allowed in the state. This makes sense in the ...
Accepted

### Why does TD Learning require Markovian domains?

The Markov assumption is used when deriving the Bellman equation for state values: $$v(s) = \sum_a \pi(a|s)\sum_{r,s'} p(r,s'|s,a)(r + \gamma v(s'))$$ One requirement for this equation to hold is that ...

### Why is the target called "target" in Monte Carlo and TD learning if it is not the true target?

It is our "current" target. We assume that the value we get now is at least a closer approximation to the "true" target. We're not so much moving towards a wrong value as we are ...
Accepted

### What is the intuition behind TD($\lambda$)?

TD($\lambda$) can be thought of as a combination of TD and MC learning, so as to avoid to choose one method or the other and to take advantage of both approaches. More precisely, TD($\lambda$) is ...

### How do temporal-difference and Monte Carlo methods work, if they do not have access to model?

The main idea is that you can estimate $V^\pi(s)$, the value of a state $s$ under a given policy $\pi$, even if you don't have a model of the environment, by visiting that state $s$ and following the ...
Accepted

### What is the typical AI approach for solving blackjack?

Blackjack is usually modelled using Monte Carlo (MC) Methods. There is a lot of literature on MC methods which is interesting on its own right but here is a paper describing how MC is applied to ...
Accepted

### Why is GLIE Monte-Carlo control an on-policy control?

In this case, $\pi$ has always been an $\epsilon$-greedy policy. In every iteration, this $\pi$ is used to generate ($\epsilon$-greedily) a trajectory from which the new $Q(s, a)$ values are ...
Accepted

### Into which subcategories can reinforcement learning be divided?

Your two suggestions are not mutually exclusive. If you go by this process, you'll have to do a "Cartesian product" of a bunch of different RL categorizations which would get out of hand. I ...
Accepted

### In MCTS, what to do if I do not want to simulate till the end of the game?

Famous example is AlphaZero. It doesn't do unrolls, but consults the value network for leaf node evaluation. The paper has the details on how the update is performed afterwards: The leaf $s'$ ...
Accepted

### Action-value estimation of deterministic policies with Monte Carlo method

But, in a real application under a given deterministic policy $\pi$, how can you choose the initial action $a$ arbitrarily at state $s$ because it is already fixed by the policy $\pi$: $a=\pi(s)$? ...

### In what RL algorithm category is MiniMax?

I think you are looking at it from the wrong direction, min-max is just a planning algorithm, decision strategy, in the sense that you are describing other algorithms/methods it does not have a ...
Accepted

### How can we compute the ratio between the distributions if we don't know one of the distributions?

The rationale behind importance sampling is that $q(x)$ is difficult to sample from but easy to evaluate. Or at least you can easily evaluate some $\tilde{q}$ such that: $$\tilde{q}(z) = Zq(z)$$ ...
Accepted

### Do we need the transition probability function when calculating the importance sampling ratio?

There is one thing I don't particularly understand. Why do we need the state-transition probability function when calculating the importance sampling ratio for off-policy prediction? It is not needed ...
Accepted

### In Monte Carlo learning, what do you do when an end state is reached, after having recorded the previously visited states and taken actions?

I am assuming you are asking about Monte Carlo simulation for value estimates, perhaps as part of a Monte Carlo control learning agent. The basic approach of all value-based methods is to estimate an ...
Accepted

### MCTS: How to choose the final action from the root

By far the most commonly used strategy is to select the child with the highest number of visits. This is as described in the 2008 paper you linked. It's also what's referred to as the "robust child" ...

### What is the relation between Monte Carlo and model-free algorithms?

In Reinforcement Learning (RL), the use of the term Monte Carlo has been slightly adjusted by convention to refer to only a few specific things. The more general use of "Monte Carlo" is for ...

### Monte-Carlo, every-visit gridworld, exploring starts, python code gets stuck in foreverloop in episode generation

Your implementation of Monte Carlo Exploring Starts algorithm appears to be working as designed. This is a problem that can occur with some deterministic policies in the gridworld environment. It is ...

### How can we compute the ratio between the distributions if we don't know one of the distributions?

It is common in Bayesian statistics to only know the posterior up to a constant of proportionality. This means that we can't directly sample from the posterior. However, using importance sample we are ...
Accepted

### What is the bias-variance trade-off in reinforcement learning?

The bias-variance trade-off that you're referring to has to do with the return estimator. Any RL algorithm you choose needs some estimate of the cumulative return, which is a random variable with many ...
Accepted

### Why are state-values alone not sufficient in determining a policy (without a model)?

why is it not possible to suggest a policy solely on the basis of state-values; why do we need state-action values? A policy function takes state as an argument and returns an action $a = \pi(s)$, or ...
Accepted

### Why does Monte Carlo policy evaluation relies on action-value function rather than state-value function?

In Model Based Reinforcement learning, state and state-action values for all states can be calculated based on the bellman equations. The equations are taken from Andrew Ng's Algorithms for Inverse ...
Accepted

### Is the expected value we sample in TD-learning action-value Q or state-value V?

However, from the blogs and texts I read, the equations are expressed in terms of V and NOT Q. Why is that? MC and TD are methods for associating value estimates to time step based on experienced ...