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

107 questions
Filter by
Sorted by
Tagged with
23 views

### Derivation in paper Deep Neural Networks as Gaussian processes in ICLR 2018

I am trying to understand the derivation of the main equation in the seminal paper titled Deep Neural Networks as Gaussian processes (in ICLR 2018). I have asked this question in https://math....
1 vote
91 views

76 views

• 509
211 views

• 203
82 views

### Is the existence and uniqueness of the state-value function for $\gamma < 1$ theoretical?

Consider the following statement from 4.1 Policy Evaluation of the first edition of Sutton and Barto's book. The existence and uniqueness of $V^{\pi}$ are guaranteed as long as either $\gamma < 1$...
• 3,251
1 vote
38 views

### Why is the number of examined nodes $O(b^{3d/4})$ in $\alpha$-$\beta$ pruning?

I'm taking a course 'Introduction to AI' and, in one of the tutorials, it was written that when pruning the game tree using $\alpha$-$\beta$ boundaries, the number of nodes that will be developed, ...
1 vote
38 views

### How to prove that a regularisation method simplified a neural network?

There are a few ways to regularise a neural network, for example dropout or the L1. Now, both these methods, and possibly most other regularisation methods, tend to remove from, or simplify the neural ...
• 206
87 views

### Is $\min(h_1(s),\ h_2(s))$ consistent?

If $h_1(s)$ is a consistent heuristic and $h_2(s)$ is a admissible heuristic, is $\min(h_1(s),\ h_2(s))$ consistent?
• 21
470 views

### Are hill climbing variations always optimal and complete?

Are hill climbing variations (like steepest ascent hill climbing, stochastic hill climbing, random restart hill climbing, local beam search) always optimal and complete? 35 views

### How is the discounted maximum entropy objective obtained for soft-q-learning and SAC

In the soft q-learning paper, they provide an expression for the maximum entropy objective that takes discounting into account. My main question is: can someone explain how they incorporated ...
• 374
1 vote
79 views

• 663
191 views

### Can a computer make a proof by induction?

Can a computer solve the following problem, i.e. make a proof by induction? And why? Prove by induction that $$\sum_{k=1}^nk^3=\left(\frac{n(n+1)}{2}\right)^2, \, \, \, \forall n\in\mathbb N .$$ I'm ...
1k views

### Why are the Bellman operators contractions?

In these slides, it is written \begin{align} \left\|T^{\pi} V-T^{\pi} U\right\|_{\infty} & \leq \gamma\|V-U\|_{\infty} \tag{9} \label{9} \\ \|T V-T U\|_{\infty} & \leq \gamma\|V-U\|_{\infty} \...
• 181
216 views

### Is the Bellman equation that uses sampling weighted by the Q values (instead of max) a contraction?

It is proved that the Bellman update is a contraction (1). Here is the Bellman update that is used for Q-Learning: Q_{t+1}(s, a) = Q_{t}(s, a) + \alpha*(r(s, a, s') + \gamma \max_{a^*} (Q_{t}(s', ...
59 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 ...
• 121
184 views

### How exactly is $Pr(s \rightarrow x, k, \pi)$ deduced by "unrolling", in the proof of the policy gradient theorem?

In the proof of the policy gradient theorem in the RL book of Sutton and Barto (that I shamelessly paste here): there is the "unrolling" step that is supposed to be immediately clear With ...
• 362
1 vote
104 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 ...
• 25
808 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-...
• 137
281 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 ...
1 vote
138 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 ...
286 views

### Is this proof of $\epsilon$-greedy policy improvement correct?

The following paragraph about $\epsilon$-greedy policies can be found at the end of page 100, under section 5.4, of the book "Reinforcement Learning: An Introduction" by Richard Sutton and ...
• 137
### How do I convert an MDP with the reward function in the form $R(s,a,s')$ to and an MDP with a reward function in the form $R(s,a)$?
The AIMA book has an exercise about showing that an MDP with rewards of the form $r(s, a, s')$ can be converted to an MDP with rewards $r(s, a)$, and to an MDP with rewards $r(s)$ with equivalent ...