# Questions tagged [proofs]

For questions that ask about or call for proofs for specific assertions, whether they be proofs of theorems or corollaries, proofs of concept through working implementation, counter proofs, or counter examples.

73 questions
Filter by
Sorted by
Tagged with
275 views

69 views

### Why does (not) the distribution of states depend on the policy parameters that induce it?

I came across the following proof of what's commonly referred to as the log-derivative trick in policy-gradient algorithms, and I have a question - While transitioning from the first line to the ...
24 views

### Do we assume the policy to be deterministic when proving the optimality?

In reinforcement learning, when we talk about the principle of optimality, do we assume the policy to be deterministic?
27 views

27 views

### What is the proof that the variance of the gradient estimate in Actor-Critic is smaller than in REINFORCE?

The intuition provided when introducing actor-critic algorithms is that the variance of its gradient estimates is smaller than in REINFORCE as, e.g., discussed here. This intuition makes sense for the ...
44 views

### When to use AND and when to use Implies in first-order logic?

I am trying to learn the theory behind first-order logic (FOL) and do some practice runs of converting statements into the form of FOL. One issue I keep running into is hesitating on whether to use an ...
79 views

### Proof of Maximization Bias in Q-learning?

In the textbook "Reinforcement Learning: An Introduction" by Richard Sutton and Andrew Barto, the concept of Maximization Bias is introduced in section 6.7, and how Q-learning "over-estimates" action-...
90 views

### What is the proof that “reward-to-go” reduces variance of policy gradient?

I am following the OpenAI's spinning up tutorial Part 3: Intro to Policy Optimization. It is mentioned there that the reward-to-go reduces the variance of the policy gradient. While I understand the ...
39 views

### How do you prove that minimax algorithm outputs a subgame-perfect Nash equilibrium?

At every node, MAX would always move to maximise the minimum payoff while MIN choose to minimise the maximum payoff, hence there is nash equilibrium. By using backwards induction, at every node, MAX ...
144 views

### Can deep learning be used to help mathematical research?

I am currently learning about deep learning and artificial intelligence and exploring his possibilities, and, as a mathematician at heart, I am inquisitive about how it can be used to solve problems ...
37 views

### Why is it hard to prove the convergence of the deep Q-learning algorithm?

Why is it hard to prove the convergence of the DQN algorithm? We know that the tabular Q-learning algorithm converges to the optimal Q-values, and with a linear approximator convergence is proved. ...
50 views

### Why is probability that at least one hypothesis out of $k$ being consistent with $m$ training examples $k(1- \epsilon)^m$?

My question is actually related to the addition of probabilities. I am reading on computational learning theory from Tom Mitchell's machine learning book. In chapter 7, when proving the upper bound ...
77 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 ...
251 views

### What is the proof that policy evaluation converges to the optimal solution?

Although I know how the algorithm of iterative policy evaluation using dynamic programming works, I am having a hard time realizing how it actually converges. It appeals to intuition that, with each ...
27 views

109 views

90 views

36 views

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
324 views

### How to show temporal difference methods converge to MLE?

In chapter 6 of Sutton and Barto (p. 128), they claim temporal difference converges to the maximum likelihood estimate (MLE). How can this be shown formally?
76 views

### Is unsupervised disentanglement really impossible?

In Locatello et al's Challenging Common Assumptions in the Unsupervised Learning of Disentangled Representations he claims to prove unsupervised disentanglement is impossible. His entire claim is ...
98 views

### Is there a rigorous proof for finding Hopfield minima?

I am looking for a rigorous mathematical proof for finding the several local minima of the Hopfield networks. I am searching for something rigorous, a demonstration, not just let the network keep ...
I don't understand the proof that $A^*$ is optimal. The proof is by contradiction: Assume $A^*$ returns $p$ but there exists a $p'$ that is cheaper. When $p$ is chosen from the frontier, assume \$...