# Questions tagged [monte-carlo]

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

49 questions
Filter by
Sorted by
Tagged with
35 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 ...
177 views

71 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?
34 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)}$?...
40 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 ...
71 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 ...
45 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 ...
99 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 ...
49 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 ...
84 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 ...
57 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 ...
24 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 ...
92 views

### In the reinforcement learning is the value of terminal/goal state always zero?

Let's assume we are in the grid world with states in a 3X3 grid numbered as 0,1,...8. If 8 is the goal state and the reward of landing in the goal state is 10 and the reward of just wandering around ...
119 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 ...
75 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 ...
183 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 ...
91 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 ...
260 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 ...
29 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 ...
149 views

### Monte Carlo learning for Reinforcement learning

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
147 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 ...
138 views

### Why does GLIE+MC Control Algorithm use a single episode of Monte Carlo evaluation?

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: ...
101 views

### How to stop evaluation phase in reinforcement learning with epsilon-greedy Monte Carlo agent?

I have implemented an epsilon-greedy Monte Carlo reinforcement learning agent like suggested in Sutton and Barto's RL book (page 101). As far as I understood epsilon-greedy agents so far, the ...
44 views

### How do I know if the assumption of a static environment is made?

An important property of a reinforcement learning problem is whether the environment of the agent is static, which means that nothing changes if the agent remains inactive. Different learning methods ...
101 views

### Why is an average of all returns used to update the value in the first-visit MC control?

In Sutton & Barto's Reinforcement Learning: An Introduction, in page 83 (101 of the pdf), there is a description of first-visit MC control. In the phase where they update $Q(s, a)$, they do an ...
147 views

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

Monte Carlo (MC) methods are methods that use some form of randomness or sampling. For example, we can use an MC method to approximate the area of a circle inside a square: we generate random 2D ...
15 views

### How is GARB implemented in PGRD-DL to calculate gradients w.r.t. internal rewards?

In section 3 of this paper the author outlines how GARB was adapted to reduce the variance in updating parameters to an internal reward function estimator. I have read it a number of times and ...
484 views

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

I've been trying to implement policy improvement for Q(s,a) function as per Sutton&Barto reinforcement learning book. The original algorithm with first-visit MonteCarlo is pictured below. I ...
262 views

### Difficulty understanding Monte Carlo policy evaluation (state-value) for gridworld

I've been trying to read Sutton & Barto book chapter 5.1, but I'm still a bit confused about the procedure of using Monte Carlo policy evaluation (p.92), and now I just cant proceed anymore coding ...
100 views

### Why is Monte Carlo used as the tree search algorithm for AlphaGo?

Could a better algorithm other than Monte Carlo be used for the AlphaGo computer? Why didn't the DeepMind team think of choosing another kind of algorithm rather than spending time on their neural ...
65 views

### Similarities and differences between UCT algorithms in (i), (ii), (iii) and (iv)?

I am trying to understand the similarities and differences between: (i) the UCT algorithm in Kocsis and SzepesvĆ”ri (2006); (ii) the UCT algorithm in Section 3.3 of Browne et al (2012); (iii) the MCTS ...
64 views

### Why didn't champion of the Go game manage to win the last game against AlphaGo, after winning the 4th one?

In the documentary about the match, it is said that after losing the 4th game, AlphaGo came back stronger and started to play in a weird way (not human-like) and it was pretty impossible to be beaten. ...
5k views

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

I came across this 2 algorithms but I cannot understand the difference between these 2 both in terms of implementation as well as intuitionally. So what difference does the second point in both the ...
104 views

### What are temporal-difference and Monte Carlo methods intuitively?

Intuitively, how do temporal-difference and Monte Carlo methods work in reinforcement learning? How can they be used to solve the reinforcement learning problem?
In slide 16 of his lecture 5 of the course "Reinforcement Learning", David Silver introduced GLIE Monte-Carlo Control. But why is it an on-policy control? The sampling follows a policy $\pi$ while ...