# Questions tagged [monte-carlo-methods]

For questions related to the Monte Carlo methods in reinforcement learning and other AI sub-fields. ("Monte Carlo" refers to random sampling of the search space.)

75 questions
Filter by
Sorted by
Tagged with
1 vote
51 views

### Given a set of trajectories produced by a fixed policy, what is the the standard approach to estimate Q?

Let's say that I have a set of trajectories $\mathcal{D} = \{\tau_1, \dots, \tau_n\}$ produced by an agent acting in a (episodic) MDP with a fixed policy $\pi$. I would like to estimate the $Q$ ...
14 views

### Given a dataset with columns $x_1, x_2, \dots, x_n, y$, which algorithm can tell me which $x$ values had the biggest impact on $y$?

I have a set of data that is generated from a monolithic Monte Carlo-based program. I've set up a way to monitor the calculations of this program and output values correlating to those calculations, ...
78 views

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

In Monte Carlo-based action value estimation problem for a deterministic policy (estimation of $q_{\pi}(s,a)$),the estimation problem seems not to be well-defined because $q_{\pi}(s,a)$ by ...
109 views

### How to code an $\epsilon$-soft policy for on-policy Monte Carlo control?

I was trying to code the on-policy Monte Carlo control method. The initial policy chosen needs to be an $\epsilon$-soft policy. Can someone tell me how to code an $\epsilon$-soft policy? I know how to ...
38 views

### How does the learning rate $\alpha$ vary in stationary and non-stationary environments?

In Sutton and Barto's book (Chapter 6: TD learning, 2nd edition), he mentions two ways of updating value function: Monte Carlo method: $V(S_t) \leftarrow V(S_t) + \alpha[G_t - V(S_t)]$. TD(0) method: ...
18 views

### In the original GAN paper, why is it claimed that variational inference is used in deep undirected models for inference?

In the original GAN paper (table 2), why is it claimed that variational inference is used in deep undirected models for inference? I was under the impression that they used Gibbs Sampling, MCMC-based ...
1 vote
45 views

### In the cross-entropy method, should I select state-action pairs by their immediate reward or by the episode reward?

I am trying to understand the code mechanics when selecting the elite states and elite actions. It appears clear to me that they are those that appear in the episodes with the rewards bigger than the ...
43 views

### Doubt in Sutton & Barto's off-policy Monte Carlo control algorithm

The algorithm is described as below: My understanding: In the third last step, we act greedily w.r.t $Q$. Since we use importance sampling, this $Q \approx Q_\pi$. However, in the next step, whenever ...
1 vote
27 views

1 vote
54 views

182 views

### Why does TD Learning require Markovian domains?

One of my friends and I were discussing the differences between Dynamic Programming, Monte-Carlo, and Temporal Difference (TD) Learning as policy evaluation methods - and we agreed on the fact that ...
190 views

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

"If a model is not available, then it is particularly useful to estimate action values (the values of state-action pairs) rather than state values. With a model, state values alone are sufficient ...
117 views

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

I've been looking online for a while for a source that explains these computations but I can't find anywhere what does the $|A(s)|$ mean. I guess $A$ is the action set but I'm not sure about that ...
1 vote
134 views

### Monte Carlo Exploring Starts broke for 2048 game AI

I implemented a MCES for 2048 (the game), with a quality function implemented as a neural net of a single layer. The starts are created with 6 cells filled with values between 64 and 1024, two cells ...
1 vote
41 views

### If the transition model is available, why would we use sample-based algorithms?

Sample-based algorithms, like Monte Carlo Algorithms and TD-Learning, are often presented as useful since they do not require a transition model. Assuming I do have access to a transition model, are ...
1 vote
41 views

### Should the importance sampling ratio be updated at the end of the for loop in the off-policy Monte Carlo control algorithm?

I'm studying RL with Sutton and Barto's book. I'd like to ask about the order of execution of a statement in the algorithm below. Here, $W$ (importance sampling ratio) is updated at the end of the <...
99 views

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

In the course of a scientific work, I will discuss the different types of reinforcement learning. However, I have difficulties to find these different types. So, into which subcategories can ...
1 vote
63 views

### Why do bootstrapping methods produce nonstationary targets more than non-bootstrapping methods?

The following quote is taken from the beginning of the chapter on "Approximate Solution Methods" (p. 198) in "Reinforcement Learning" by Sutton & Barto (2018): reinforcement ...
799 views

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

I am watching DeepMind's video lecture series on reinforcement learning, and when I was watching the video of model-free RL, the instructor said the Monte Carlo methods have less bias than temporal-...
374 views

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

Here is my understanding of importance sampling. If we have two distributions $p(x)$ and $q(x)$, where we have a way of sampling from $p(x)$ but not from $q(x)$, but we want to compute the expectation ...
152 views

### How is the incremental update rule derived from the weighted importance sampling in off-policy Monte Carlo control?

Here's the approximated value using weighted importance sampling $$V_{n} \doteq \frac{\sum_{k=1}^{n-1} W_{k} G_{k}}{\sum_{k=1}^{n-1} W_{k}}, \quad n \geq 2$$ Here's the incremental update rule for ...
270 views

### In what RL algorithm category is MiniMax?

Q-learning is a temporal-difference method and Monte Carlo tree search is a Monte Carlo method. In what category is MiniMax?
46 views

### Why do we update $W$ with $\frac{1}{\mu (A_t | S_t)}$ instead of $\frac{\pi (A_t | S_t)}{\mu (A_t | S_t)}$ in off-policy Monte Carlo control?

I had the same question when I am reading the RL textbook from Sutton Bartol as posted here. Why do we update $W$ with $\frac{1}{\mu (A_t | S_t)}$ instead of $\frac{\pi (A_t | S_t)}{\mu (A_t | S_t)}$?...
1 vote
77 views

### When does Monte Carlo linear function approximation converge?

In this Stanford lecture (minute 35:47 and 37:00), the professor says that Monte Carlo (MC) linear function approximation does not always converge, and she gives an example. In general, when does MC ...
1 vote
233 views

### Monte Carlo epsilon-greedy Policy Iteration: monotonic improvement for all cases or for the expected value?

I was going through university slides and this particular slide is trying to prove that in a Monte Carlo Policy Iteration algorithm using an epsilon-greedy policy, the state Values (V-Values) are ...
1 vote
67 views

### Understanding the W term in off policy monte carlo learning

In Sutton and Barto's RL textbook they included the following pseudocode for off policy Monte Carlo learning. I am a little confused, however, because to me it looks like the W term will become ...
1k views

### How does Monte Carlo Exploring Starts work?

I'm having trouble understanding the 5th step in the flowchart. For the 5th step, the 'update the Q function by taking the average of returns' is confusing. From what I understand, the Q function ...
1 vote
115 views

### MCTS moves with multiple parents

I'd like to develop an MCTS-like (Monte Carlo Tree Search) algorithm for program induction, i.e. learning programs from examples. My initial plan is for nodes to represent programs and for the search ...
314 views

### How to apply hyperparameter optimization on Monte Carlo Tree Search?

I have a basic MCTS agent for the game of Hex (a turn based game). I want to tune the parameters of UCT (the Cp parameter) and the number of rollouts parameter. Where do I have to begin? The problem ...
223 views

### How does policy evaluation work for continuous state space model-free approaches?

How does policy evaluation work for continuous state space model-free approaches? Theoretically, a model-based approach for the discrete state and action space can be computed via dynamic programming ...
455 views

### How does Monte Carlo have high variance?

I was going through David Silver's lecture on reinforcement learning (lecture 4). At 51:22 he says that Monte Carlo (MC) methods have high variance and zero bias. I understand the zero bias part. It ...
### What is the intuition behind TD($\lambda$)?
I'd like to better understand temporal-difference learning. In particular, I'm wondering if it is prudent to think about TD($\lambda$) as a type of "truncated" Monte Carlo learning?