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.

Filter by
Sorted by
Tagged with
2
votes
1answer
122 views

Is there a mathematical theory behind why MLP can classify handwritten digits?

I'm trying to really understand how multi-layer perceptrons work. I want to prove mathematically that MLP's can classify handwritten digits. The only thing I really have is that each perceptron can ...
1
vote
1answer
65 views

Can the law of iterated expectation be used on the inner expectation of the DQN cost function described in the DQN paper

Is the expression for the DQN cost function, Equation (2) of the DQN paper $$\begin{align}L_1 &= E_{\mu,\pi}\left[\left(y_i - q(s,a;\theta)\right)^2\right]\\ &=E_{\mu,\pi}\left[\left(E_{\...
2
votes
1answer
70 views

If $h_1(n)$ is admissible, why does A* tree search with $h_2(n) = 3h_1(n)$ return a path that is at most thrice as long as the optimal path?

Consider a heuristic function $h_2(n) = 3h_1(n)$. Where $h_1(n)$ is admissible. Why are the following statements true? $A^*$ tree search with $h_2(n)$ will return a path that is at most thrice as ...
0
votes
1answer
43 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?
0
votes
0answers
21 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 ...
4
votes
1answer
140 views

Does Rice's theorem prove safe AI is undecidable?

According to Wikipedia In computability theory, Rice's theorem states that all non-trivial, semantic properties of programs are undecidable. A semantic property is one about the program's ...
4
votes
2answers
82 views

What is the proof that the branch and bound algorithm always finds optimal path in a graph?

I've been studying Branch and Bound's graph algorithm and I hear it always finds the optimal path because it uses previously found solutions to find others However, I haven't been able to find a ...
5
votes
2answers
186 views

Why is “-0.5 * torch.sum(1 + sigma - mu.pow(2) - sigma.exp())” in Pytorch equivalent to the KL?

I found this code for the loss function of a VAE: -0.5 * torch.sum(1 + sigma - mu.pow(2) - sigma.exp()) From this link: https://debuggercafe.com/getting-started-...
2
votes
1answer
499 views

Why isn't Nilsson's Sequence Score an admissible heuristic function?

I understand what an admissible heuristic is, I just don't know how to tell whether one heuristic is admissible or not. So, in this case, I'd like to know why Nilsson's sequence score heuristic ...
4
votes
1answer
514 views

How does L2 regularization make weights smaller?

I'm learning logistic regression and $L_2$ regularization. The cost function looks like below. $$J(w) = -\displaystyle\sum_{i=1}^{n} (y^{(i)}\log(\phi(z^{(i)})+(1-y^{(i)})\log(1-\phi(z^{(i)})))$$ And ...
3
votes
1answer
123 views

Is my proof of equation 0.6 in the book “Reinforcement Learning: Theory and Algorithms” correct?

In Sham Kakade's Reinforcement Learning: Theory and Algorithms, this equation (page 17) is used preceding the proof of performance difference lemma. I am attempting to prove equation 0.6. Here is my ...
5
votes
2answers
223 views

How are the reward functions $R(s)$, $R(s, a)$ and $R(s, a, s')$ equivalent?

In this video, the lecturer states that $R(s)$, $R(s, a)$ and $R(s, a, s')$ are equivalent representations of the reward function. Intuitively, this is the case, according to the same lecturer, ...
16
votes
3answers
5k views

Where can I find the proof of the universal approximation theorem?

The Wikipedia article for the universal approximation theorem cites a version of the universal approximation theorem for Lebesgue-measurable functions from this conference paper. However, the paper ...
5
votes
1answer
224 views

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 ...
4
votes
0answers
67 views

When do two identical neural networks have uncorrelated errors?

In Chapter 9, section 9.1.6, Raul Rojas describes how committees of networks can reduce the prediction error by training N identical neural networks and averaging the results. If $f_i$ are the ...
2
votes
1answer
94 views

How to prove the formula of eligibility traces operator in reinforcement learning?

I don't understand how the formula in the red circle is derived. The screenshot is taken from this paper
2
votes
1answer
264 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-...
1
vote
1answer
355 views

Is there a proof to explain why XOR cannot be linearly separable?

Can someone explain to me with a proof or example why you can't linearly separate XOR (and therefore need a neural network, the context I'm looking at it in)? I understand why it's not linearly ...
11
votes
5answers
3k views

Is there a rigorous proof that AGI is possible, at least, in theory?

It is often implicitly assumed in computer science that the human mind, or at least some mechanical calculations that humans perform (see the Church-Turing thesis), can be replicated with a Turing ...
2
votes
0answers
23 views

Does there necessarily exist “dominated actions” in a MDP?

In a Markov Decision Process, is it possible that there exists no "dominated action"? I define a dominated action the following way: we say that $(s,a)$ is a dominated action, if $\forall \...
1
vote
1answer
236 views

Why does Q-learning converge to the optimal policy, even if the agent acts sub-optimally?

In Q-learning, during training, it doesn't matter how the agent selects actions. The algorithm always converges to the optimal policy. Why does this happen? What's the intuition?
1
vote
1answer
29 views

How do I prove that the MSE is zero when all predictions are equal to the corresponding labels?

In the back-propogation algorithm, the error term is: $$ E=\frac{1}{2}\sum_k(\hat{y}_k - y_k)^2, $$ where $\hat{y}_k$ is a vector of outputs from the network, $y_k$ is the vector of correct labels (...
17
votes
3answers
2k views

Why doesn't Q-learning converge when using function approximation?

The tabular Q-learning algorithm is guaranteed to find the optimal $Q$ function, $Q^*$, provided the following conditions (the Robbins-Monro conditions) regarding the learning rate are satisfied $\...
0
votes
0answers
17 views

Is the PR AUC invariant under label flip?

The ROC-AUC curve is invariant under a flip of the labels. I don't know if it's a famous result, so I will give the proof below. My question is if the PR-AUC curve also has this property. I have not ...
3
votes
1answer
107 views

Understanding proof of lemma 1 (policy improvement bound) of the “Trust Region Policy Optimization” paper

In the Trust Region Policy Optimization paper, in Lemma 1 of Appendix A, I did not quite understand the transition from (21) from (20). In going from (20) to (21), $A^\pi(s_t, a_t)$ is substituted ...
6
votes
1answer
165 views

Why does a negative reward for every step really encourage the agent to reach the goal as quickly as possible?

If we shift the rewards by any constant (which is a type of reward shaping), the optimal state-action value function (and so optimal policy) does not change. The proof of this fact can be found here. ...
2
votes
2answers
529 views

If uniform cost search is used for bidirectional search, is it guaranteed the solution is optimal?

If uniform cost search is used for both the forward and backward search in bidirectional search, is it guaranteed the solution is optimal?
5
votes
2answers
307 views

Given two optimal policies, is an affine combination of them also optimal?

If there are two different optimal policies $\pi_1, \pi_2$ in a reinforcement learning task, will the linear combination (or affine combination) of the two policies $\alpha \pi_1 + \beta \pi_2, \alpha ...
1
vote
0answers
31 views

How can I derive n-step off-policy temporal difference formula?

I was reading the book "Reinforcement Learning: An Introduction" by Sutton and Barto. In section 7.3, they write the formula for n-step off-policy TD as $$V(S_t) = V(S_{t-1}) + \alpha \rho_{...
0
votes
1answer
111 views

What is the optimal value function of the shifted version of the reward function?

Similarly to this question that I asked some time ago, what is the optimal value function of the shifted (by some constant $c$) version of some reward function? More precisely, let's assume that $r(s, ...
2
votes
1answer
279 views

What is the optimal value function of the scaled version of the reward function?

Consider the reward function $r(s, a)$ with optimal state-action value function $q_*(s, a)$. What would be the optimal state-action value function of $c r(s, a)$, for $c \in \mathbb{R}$? Would it be $...
2
votes
0answers
113 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 ...
3
votes
2answers
74 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 ...
2
votes
0answers
25 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?
5
votes
2answers
144 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} \...
0
votes
0answers
63 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 ...
2
votes
1answer
517 views

Is there a simple proof of the convergence of TD(0)?

Does anybody know a simple proof of the convergence of the TD(0) value function prediction algorithm?
6
votes
0answers
157 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', ...
1
vote
0answers
28 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 ...
1
vote
1answer
48 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 ...
9
votes
2answers
779 views

Why is baseline conditional on state at some timestep unbiased?

In the homework for the Berkeley RL class, problem 1, it asks you to show that the policy gradient is still unbiased if the baseline subtracted is a function of the state at time step $t$. $$ \...
5
votes
1answer
152 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 ...
1
vote
0answers
75 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 ...
4
votes
3answers
1k views

Is there a mathematical proof that shows that certain parameters work “better” than others for a certain task?

The machine learning community often only provides empirical results, but I am also interested in theoretical results and proofs. Specifically, is there a mathematical proof that shows that certain ...
11
votes
2answers
1k views

How do we prove the n-step return error reduction property?

In section 7.1 (about the n-step bootstrapping) of the book Reinforcement Learning: An Introduction (2nd edition), by Andrew Barto and Richard S. Sutton, the authors write about what they call the "n-...
1
vote
1answer
51 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 ...
1
vote
1answer
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 ...
5
votes
2answers
474 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 ...
2
votes
1answer
34 views

Equivalence between expected parameter increments in “Off-Policy Temporal-Difference Learning with Function Approximation”

I am having a hard time understanding the proof of theorem 1 presented in the "Off-Policy Temporal-Difference Learning with Function Approximation" paper. Let $\Delta \theta$ and $\Delta \...
2
votes
1answer
48 views

Is the derivative of the loss wrt a single scalar parameter proportional to the loss?

I am wondering about the correlation between the loss and the derivative of the loss wrt a single scalar parameter, with the same sample. That means: considering a machine learning model with ...