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

64 questions
Filter by
Sorted by
Tagged with
79 views

### With Monte Carlo off-policy learning what do we correct by using importance sampling?

I do not understand the link of importance sampling to Monte Carlo off-policy learning. We estimate a value using sampling on whole episodes, and we take these values to construct the target policy. ...
50 views

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

I'm trying to implement MCTS with UCT for a board game and I'm kinda stuck. The state space is quite large (3e15), and I'd like to compute a good move in less than 2 seconds. I already have MCTS ...
31 views

### Are regret values in each block of MC external sampling stored in each node of the block we are traversing down (denoted by $\{Q_1,…, Q_n\}$)?

Everything I know about Monte Carlo counterfactual regret minimization (CFR) comes from the paper Monte Carlo Sampling for Regret Minimization in Extensive Games by Marc Lanctot et al. So, I will use ...
70 views

### How exactly is Monte Carlo counterfactual regret minimization with external sampling implemented?

I have read many papers, such as this or this, explaining how external sampling works, but I still don't understand how the algorithm works. I understand you divide $Q$, which is the set of all ...
56 views

### What are the popular approaches to estimating the Q-function?

I need the q-value for my RL training, there are some approaches: Brute-force the action sequence (this won't work for long sequence) Use a classic algorithm to optimise and estimate (this ain't much ...
47 views

### How can I use Monte Carlo Dropout in a pre-trained CNN model?

In Monte Carlo Dropout (MCD), I know that I should enable dropout during training and testing, then get multiple predictions for the same input $x$ by performing multiple forward passes with $x$, then,...
121 views

### Why do we need importance sampling?

I was studying the off-policy policy improvement method. Then I encountered importance sampling. I completely understood the mathematics behind the calculation, but I am wondering what is the ...
55 views

### When updating the state-action value in the Monte Carlo method, is the return the same for each state-action pair?

Referring to this post, in the following formula to update the state-action value $$Q(s,a) = Q(s,a) + \alpha (G − Q(s,a)),$$ is the value of $G$ (the return) the same for every state-action $(s,a)$ ...
35 views

### Unclear definition of a “leaf” and diverging UTC values in the Monte Carlo Tree Search

I have two questions regarding the Selection and Expansion steps in the Monte Carlo Tree Search Algorithm. In order to state the questions, I recall the algorithm that I believe is the one most ...
60 views

### Is my pseudocode titled “Monte Carlo Exploring Starts (with model)” correct?

Reinforcement Learning: An Introduction second edition, Richard S. Sutton and Andrew G. Barto: We made two unlikely assumptions above in order to easily obtain this guarantee of convergence for the ...
42 views

### When we have multiple traces, do we average over traces or the total number of times we have visited that state?

I am confused about the workings of the first- and every-visit MC. My first question is, when we have multiple traces, do we average over traces or the total number of times we have visited that state?...
21 views

### Suppose every-visit MC was used instead of first-visit MC on blackjack. Would you expect the results to be different?

This is a question from page 94 of Sutton and Barto's RL book 2020. I read in someone's compiled GitHub answers to this book's exercises their answer was: "No because each state in an episode of ...
104 views

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

Both MC and TD are model-free and they both follow a sample trajectory (in the case of TD, the trajectory is cut-short) to estimate the return (we basically are sampling Q values). Other than that, ...
99 views

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

Here is David Silver's lecture on that. Look at 9:30 to 10:30. He says that, since it is model-free learning, the environment's dynamics are unknown, so the action-value function $Q$ is used. But ...
61 views

### AI to play a solo card game

I would like to create an AI for the 1 player version of the card game called "The Game" by Steffen Benndorf (rules here: https://nsv.de/wp-content/uploads/2018/05/the-game-english.pdf). The ...
44 views

### How to prove variance infinite of monte carlo ordinary importance sampling estimator

In example 5.5 of Sutton and Barto's book for proving infinite variance of first visit monte carlo ordinary importance sampling estimator, $\mathbb{E}[(\Pi_t\frac{\pi(A_t|S_t)}{b(A_t|S_t)}G_0)^2]$ is ...
192 views

113 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?
37 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)}$?...
53 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 ...
116 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 ...
46 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 ...
242 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 ...
72 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 ...
147 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 ...
69 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 ...
33 views

### In reinforcement learning what do we mean by a model? [duplicate]

I was going through the chapter "Monte Carlo Methods" from the book "Reinforcement Learning" by Sutton and Barto. The author says that when a model is not available then it is useful to estimate ...
183 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 ...
100 views

### What does the figure “Blackjack Value Function…” from Sutton represent?

I came across this graph in David Silver's youtube lecture and Sutton's book on reinforcement learning. Can anyone help me understand the graph? From the graph, for 10000 episodes what i see is ...
512 views

### 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?
39 views

### Why is this Monte Carlo approach scalable for a growing number of states variables and action variables?

I am reading a research paper on the formulation of MDP problems to ICU treatment decision making: Treatment Recommendation in Critical Care: A Scalable and Interpretable Approach in Partially ...
120 views

### Why Monte Carlo epsilon-soft approach cannot compute $\max Q(s,a)$?

I am new to Reinforcement learning and am currently reading up on the estimation of Q $\pi(s, a)$ values using MC epsilon-soft approach and chanced upon this algorithm. The link to the algorithm is ...
499 views

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

When the time allotted to Monte Carlo tree search runs out, what action should be chosen from the root? The original UCT paper (2006) says bestAction in their ...
31 views

### Can I use my previous estimate of the state-action values as initialisation in GLIE-Monte Carlo Control?

I am trying to implement a tabular-based GLIE Monte-Carlo learning algorithm. So I repeat n times: create observations using my previous policy $\pi_{n-1}(s)$ update my state-action values using ...
212 views

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

When you train a model using Monte Carlo-based learning the state and action taken at each step is recorded, and then at some point an end state is reached and the agent receives some reward - what do ...
43 views

### How to show Monte Carlo methods converge to an estimate which minimizes mean squared error?

In chapter six of Sutton and Barto (p.128), they claim Monte Carlo methods converge to an estimate minimizing the mean squared error. How can this be shown formally? Bump
223 views

### How is Monte Carlo different from model-based methods?

I was going through an article where it is mentioned: The Monte-Carlo methods require only knowledge base (history/past experiences)—sample sequences of (states, actions and rewards) from the ...
GLIE+MC control Algorithm: My question is why does this algorithm use only a single Monte Carlo episode (during PE step) to compute the $Q(s,a)$? In my understanding this has the following drawbacks: ...