Questions tagged [function-approximation]
For questions related to the concept of function approximation. For example, questions that involve the use of a neural network (which is a function approximator) in the context of RL in order to approximate a value function or questions that are related to universal approximation theorems.
90
questions
3
votes
1
answer
80
views
Why do big policy updates cause performance drop in deep RL?
In the TRPO and PPO papers, it is mentioned that large policy updates often lead to performance drops in policy gradient methods.
By "large policy updates," they mean a significant KL ...
- 191
0
votes
0
answers
35
views
Is it possible to know the family of functions a neural network approximates?
Is it possible somehow to find which family of functions a particular network approximates?
For example, I have some directed graph and I use its vertices as artificial neurons (as simple McCulloch &...
- 101
4
votes
1
answer
229
views
Why policy improvement theorem can't be applied in case of function approximation?
Policy improvement theorem is proven as follows:
$$v_\pi(s) = \sum_{a \in A} \pi(a|s)q_\pi(a,s) \leq \max_{a \in A} q_\pi(a,s) = q_\pi(\pi'(s), s)$$
What step of the proof does not hold for function ...
- 143
0
votes
0
answers
16
views
Periodic feature layer for Lotka-Volterra approximation
I am working with DeepXDE, a SciML library that can be used to solve differential equations. I came across this demo page for solving a Lotka-Volterra system. Since the solutions are known to be ...
0
votes
0
answers
49
views
What else could I try to avoid catastrophic forgetting in my implementation of Semi-Gradient SARSA?
I was trying to implement the semi-gradient SARSA algorithm (see p.244 Reinforcement Learning: An Introduction) using PyTorch:
...
- 195
0
votes
2
answers
219
views
Can an RNN predict a sinus curve with no input?
I read a number of tutorials on how to make an RNN (simple, LSTM, etc.) that predicts a sinus curve. They all use as an input (x) in every step a set of past sinus values.
I am wondering if ...
1
vote
0
answers
46
views
Can we use Low rank approximation in Markov decision process problem?
I am newbie in MDP.I have started reading Ronald Howard Dynamic Programming and MDP book as well as Sutton and Barto An Introduction to Reinforcement Learning. To my understanding MDP is a model based ...
1
vote
1
answer
140
views
Is there a mathematical proof of the universal approximation theorem for neural networks with binary weights?
Since the Universal approximation theorem shows that standard multilayer feedforward networks with as few as a single hidden layer, sufficient hidden units, and arbitrary bounded and nonconstant ...
- 33
4
votes
1
answer
515
views
Why are policy gradient methods more effective in high-dimensional action spaces?
David Silver argues, in his Reinforcement Learning course, that policy-based reinforcement learning (RL) is more effective than value-based RL in high-dimensional action spaces. He points out that the ...
- 143
0
votes
1
answer
65
views
A practice neural network to find maximum values from subset
I have an input vector of shape say 1 x 400. It's fed into a network that outputs a 1 x 100 vector. I want to design a model that only considers every 4th value of this tensor and gives me the max ...
- 65
2
votes
1
answer
2k
views
The reason behind using MCTS over Alpha Beta Pruning in Alphazero
I am not really satisfied with the available analysis of why AlphaZero uses MCTS instead of Alpha Beta search.
Some analysis claim that its because MCTS is a lot more humanlike. I disagree because I ...
- 123
1
vote
2
answers
68
views
Can I minimize a mysterious function by running a gradient descent on her neural net approximations?
So I have this function let call her $F:[0,1]^n \rightarrow \mathbb{R}$ and say $10 \le n \le 100$. I want to find some $x_0 \in [0,1]^n$ such that $F(x_0)$ is as small as possible. I don't think ...
- 111
-1
votes
1
answer
838
views
PRNG Function Prediction [duplicate]
Can any machine learning algorithm predict the function of pseudo random number generator given only its inputs and outputs?
Here, you can also assume that you don't know the seed for the PRNG.
- 1
5
votes
1
answer
213
views
Why are only neural networks (and not SVMs, for example) used for reinforcement learning?
I know that neural networks are the "universal function approximator", but they also have a huge number of trainable parameters and are extremely prone to overfitting.
So my question is: Why ...
- 362
3
votes
1
answer
399
views
Why does the average-reward estimator for continuing tasks use the TD error?
In Sutton and Barto's RL book, section 10.3 describes how to use average reward $r(\pi)$ to define the quality of a policy, re-defining action-value function $q_\pi(s,a)$ and value function $v_\pi(s)$ ...
- 106
0
votes
1
answer
124
views
Could Softmax Action Selection be useful to solve an episodic task with more than 100000 possible states and 2000 actions?
I am new in the field of RL. I am trying to use tabular methods, Q-Learning for solving a problem that takes a lot of time for computation, so I would like to know if there are more efficient methods ...
- 33
1
vote
0
answers
54
views
Knowing the futility of discounting in continuing problems, how can we say discounting has no role in control problems with function approximation?
Sutton-Barto (Section 10.4, page 254):
Based on the futility of discounting in continuing problems, how can we conclude that discounting has no role to play in control problems with function ...
- 199
1
vote
0
answers
41
views
Why is the step-size $\alpha_t = 1/t$ not appropriate for non-stationary function approximation?
Sutton-Barto (Section: Selecting Step-Size Parameters Manually, page: 222)
The classical choice $\alpha_t = 1/t$, which produces sample averages in tabular MC methods, is not appropriate for TD ...
- 199
-1
votes
1
answer
72
views
Unclear points for polynomial basis for function approximation [closed]
I have 3 questions for the following box from Sutton-Barto's RL book (page 211) on polynomial basis:
Q1- Why is each $x_i$ an "order-n" polynomial? I think this is wrong: in my opinion, ...
- 974
1
vote
0
answers
34
views
What is the difference between the $Q_a$ calculated to update delta and those to select next action in the exploitation phase?
As the title suggests, I have a doubt about the computation of the $Q_a$ used to update the delta and the $Q_a$ used to select the next action in the exploitation phase, as shown below (source of ...
2
votes
0
answers
168
views
Watkins' Q(λ) with function approximation: why is gradient not considered when updating eligibility traces for the exploitation phase?
I'm implementing the Watkins' Q(λ) algorithm with function approximation (in 2nd edition of Sutton & Barto).
I am very confused about updating the eligibility traces because, at the beginning of ...
0
votes
1
answer
283
views
Alternatives to neural networks for function approximation in Q learning?
I want to know if there is anything other than neural networks (or Deep NNs) that I can effectively use to perform function approximation? I am asking this w.r.t to the use of approximators in Q ...
0
votes
0
answers
162
views
What do we actually 'approximate' when dealing with large state spaces in Q-learning?
I realized that my state space is very large in size. I had planned to use tabular Q-learning (Bellman equation to update the $Q(s, a)$ after each action taken). But this 'large space' realization has ...
5
votes
1
answer
226
views
In TD(0) with linear function approximation, why is the gradient of $\hat v(S^{\prime}, \mathbf w)$ wrt parameters $\mathbf w$ not considered?
I am reading these slides. On page 38, the update for the parameters for the linear function approximation of TD(0) is given. I have a doubt regarding this.
The cost function (RMSE) is given on page ...
- 53
2
votes
0
answers
138
views
Does there exist functions for which the necessary number of nodes in a shallow neural network tends to infinity as approximation error tends to 0?
The Universal Approximation Theorem states (roughly) that any continuous function can be approximated to within an arbitrary precision $\varepsilon>0$ by a feedforward neural network with one ...
- 23
0
votes
0
answers
48
views
Uniform representation of images for machine learning
I'm new to the field of ML so please bear with me while I try to explain what I'm looking for. In most machine learning pipelines that deal with images there is a requirement to "normalize" ...
1
vote
1
answer
1k
views
Why use sin/cos to give periodicity in time series prediction
In this tutorial https://www.tensorflow.org/tutorials/structured_data/time_series#feature_engineering (scroll down a bit to "Time" heading), they take the sin/cos of the time index, and give ...
- 1,301
1
vote
0
answers
50
views
Is it true that real world data is highly discontinuous?
A function $f$ is said to be continuous at a point $c$ if it satisfies three properties:
Should be defined at the point $c$
Left and right-hand limits at $c$ must be equal i.e., the limit must exist
...
- 3,960
2
votes
1
answer
112
views
Is Reinforcement Learning capable of learning complex functions (such as producing a 3d model given an image)?
I want to build an AI that can convert an image of a subject into an anatomically accurate 3D model. To do this, I was thinking of adapting the following code for Deep Deterministic Policy Gradient: ...
- 21
2
votes
1
answer
99
views
Recursive Least squares (RLS) for mini batch
For my application I am considering a learning problem where I simulate a bunch of episodes say '$n$' first, and than carry out the recursive least squares update. Similar to $TD(1)$.
I know that RLS ...
1
vote
0
answers
29
views
Is it possible to compute the logical AND and OR with logistic regression?
It's easy to build a perceptron that can compute the logical AND and OR functions of its binary inputs.
Logistic regression could be used as a binary classifier.
$$z^{(i)} = w^T x^{(i)} + b$$
$$\hat{y}...
- 221
2
votes
2
answers
474
views
Why is the equation $\mathbb{E} \left[ (Y - \hat{Y})^2 \right] = \left(f(X) - \hat{f}(X) \right)^2 + \operatorname{Var} (\epsilon)$ true?
In the book An Introduction to Statistical Learning, the authors claim (equation 2.3, p. 19, chapter 2)
$$\mathbb{E} \left[ (Y - \hat{Y})^2 \right] = \left(f(X) - \hat{f}(X) \right)^2 + \operatorname{...
- 41.1k
1
vote
0
answers
81
views
Is there any thumb rule on the cardinality of state space in order to use the parameterized function to estimate value functions?
Value functions for a given MDP can be learned in at least two ways by experience.
The first way (tabular calculation) is generally used in the case of state spaces that are small enough.
The second ...
- 3,960
1
vote
2
answers
98
views
Trying to understand why nonlinearity is important for neural networks by analogy
Is the reason why linear activation functions are usually pretty bad at approximating functions the same reason why combinations of hermitian polynomials or combinations of sines and cosines are ...
- 39
0
votes
2
answers
306
views
Why can a neural network use more than one activation function?
From trying to understand neural networks better, I've come upon a tentative notion that an activation function aims to build a function it's approximating via linear combinations with biases and ...
- 39
-2
votes
1
answer
981
views
Why the optimal Bellman operator of a Q-function can be approximated by a single point
I am currently studying reinforcement learning, especially DQN.
In DQN, learning proceeds in such a way as to minimize the norm (least-squares, Huber, etc.) of the optimal Bellman equation and the ...
- 97
1
vote
2
answers
37
views
How can "any process you can imagine" be thought of as function computation?
I stumbled upon this passage when reading this guide.
Universality theorems are a commonplace in computer science, so much
so that we sometimes forget how astonishing they are. But it's worth
...
- 39
2
votes
0
answers
93
views
How to find good features for a linear function approximation in RL with large discrete state set?
I've recently read much about feature engineering in continuous (uncountable) feature spaces. Now I am interested what methods exist in the setting of large discrete state spaces. For example consider ...
- 121
0
votes
1
answer
86
views
Is it possible to predict $x^2$, $\log(x)$, or variable function of $x$ using RNN?
There were some posts that using RNN can predict the next point of the sine wave function with data history.
However, I wondered if it also works on all the functions of $x$, such as $x^2$, $x^3$, $\...
8
votes
2
answers
4k
views
What is the relation between the context in contextual bandits and the state in reinforcement learning?
Conceptually, in general, how is the context being handled in contextual bandits (CB), compared to states in reinforcement learning (RL)?
Specifically, in RL, we can use a function approximator (e.g. ...
- 183
1
vote
2
answers
783
views
Can stochastic gradient descent be properly used in any sample based learning algorithm in Reinforcement Learning?
Assuming we use an MSE cost function of the form
$$ \sum_s\mu(s)(V_{\pi}(S_t)-\hat{V}(S_t,\theta_t))^2 = E_{\mu(s)}[(V_{\pi}(S_t)-\hat{V}(S_t,\theta_t))^2])$$
The Stochastic Gradient Descent is used ...
- 394
1
vote
0
answers
434
views
Can someone explain to me this implementation of Tile Coding using Hash Tables?
The code below is adapted from this implementation.
...
- 111
1
vote
0
answers
58
views
Are monotonically increasing functions easier to learn?
A monotonically increasing function is a function that as x gets bigger so does its output. So, if plotted, it will never go down. Although the outputs might stay constant.
Logically this seems like ...
- 236
1
vote
0
answers
54
views
What is the smallest upper bound for a number of functions in a range that are computable by a perceptron?
I'm reading this book chapter, and I'm looking at the questions on the last page. Can someone explain question 2 on the last page to me, or show me an example of a solution so I can understand it?
The ...
- 307
20
votes
1
answer
1k
views
What is the number of neurons required to approximate a polynomial of degree n?
I learned about the universal approximation theorem from this guide. It states that a network even with a single hidden layer can approximate any function within some bound, given a sufficient number ...
- 793
4
votes
1
answer
113
views
How does uniform offset tiling work with function approximation?
I get the fundamental idea of how tilings work, but, in Barton and Sutton's book, Reinforcement Learning: An Introduction (2nd edition), a diagram, on page 219 (figure 9.11), showing the variations of ...
- 394
1
vote
0
answers
27
views
Neural network architecture with inputs and outputs being an unkown function each
I am trying to set up a neural network architecture that is able to learn the points of one function (blue curves) from the points of an other one (red curves). I think that it could be somehow ...
- 31
4
votes
1
answer
272
views
Can models get 100% accuracy on solved games?
I had a question today that I feel it must have an answer already, so I'm shopping around.
If we ask a model to learn the binary OR function, we get perfect accuracy with every model (as far as I know)...
- 141
6
votes
1
answer
539
views
Smallest possible network to approximate the $sin$ function
The main goal is: Find the smallest possible neural network to approximate the $sin$ function.
Moreover, I want to find a qualitative reason why this network is the smallest possible network.
I have ...
- 75
2
votes
1
answer
80
views
Why is the fraction of time spent in state $s$, $\mu(s)$, not in the update rule of the parameters?
I am reading "Reinforcement Learning: An Introduction (2nd edition)" authored by Sutton and Barto. In Section 9, On-policy prediction with approximation, it first gives the mean squared ...
- 123