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.

Filter by
Sorted by
Tagged with
1
vote
0answers
15 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
0answers
19 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}...
5
votes
2answers
4k views

Can a neural network with linear activation functions produce a connection of linear functions?

From a lecture in machine learning, I know that a linear activation function can only produce a linear function, but I don't know if it can produce a connected linear function, like the one in the ...
3
votes
2answers
839 views

Why use semi-gradient instead of full gradient in RL problems, when using function approximation?

Semi-gradient methods work well in reinforcement learning, but what is there a reason of not using the true gradient if it can be computed? I tried it on the cart pole problem with a deep Q-network ...
0
votes
1answer
63 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 ...
2
votes
2answers
124 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{...
1
vote
0answers
20 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 ...
0
votes
0answers
15 views

Can transformers be used to improve regression?

I was recently reading a bit about transformers and I don't understand them very much but I was wondering if anyone knows if any of their techniques such as attention mechanism or anything has been ...
1
vote
2answers
32 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 ...
4
votes
1answer
114 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)...
-2
votes
1answer
62 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 ...
1
vote
2answers
35 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 ...
2
votes
0answers
306 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. ...
0
votes
0answers
107 views

Remove drawbacks of Neural Network regressor as compared Polynomial Regressor

As far as my knowledge goes (might be a bit vague and not mathematical), a Neural Network can and should only be able to approximate a bounded function, which is not the case of a Polynomial Regressor....
2
votes
0answers
27 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 ...
0
votes
1answer
80 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$, $\...
5
votes
2answers
209 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. ...
1
vote
2answers
168 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 ...
2
votes
0answers
37 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 ...
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 ...
6
votes
1answer
111 views

Why are neural networks preferred to other classification functions optimized by gradient decent

Consider a neural network, e.g. as presented by Nielsen here. Abstractly, we just construct some function $f: \mathbb{R}^n \to [0,1]^m$ for some $n,m \in \mathbb{N}$ (i.e. the dimensions of the input ...
2
votes
0answers
44 views

Does coarse coding with radial basis function generate fewer features?

I am learning about discretization of the state space when applying reinforcement learning to continuous state space. In this video the instructor, at 2:02, the instructor says that one benefit of ...
1
vote
0answers
73 views

Can someone explain to me this implementation of Tile Coding using Hash Tables?

The code below is adapted from this implementation. ...
3
votes
0answers
157 views

When using hashing in tile coding, why are memory requirements reduced and there is only a little loss of performance?

In the book "Reinforcement Learning: An Introduction" (2018) Sutton and Barto explain, on page 221, a form of tile coding using hashing, to reduce memory consumption. I have two questions ...
5
votes
2answers
217 views

Is a multilayer perceptron a recursive function?

I read somewhere that a multilayer perceptron is a recursive function in its forward propagation phase. I am not sure, what is the recursive part? For me, I would see an MLP as a chained function. So, ...
0
votes
0answers
16 views

Is parameter sharing in AlBERT akin to repeated application of same function on input?

I read the AlBERT and saw that its architecture used "Parameter Sharing" among layers of the encoder. They mentioned that this was done to save model space, make fewer training parameters ...
8
votes
3answers
1k views

Are ReLUs incapable of solving certain problems?

Background I've been interested in and reading about neural networks for several years, but I haven't gotten around to testing them out until recently. Both for fun and to increase my understanding, I ...
1
vote
0answers
33 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 ...
2
votes
3answers
121 views

Is there a way to calculate the closed-form expression of the function that a neural network computes?

As stated in the universal approximation theorem, a neural network can approximate almost any function. Is there a way to calculate the closed-form (or analytical) expression of the function that a ...
1
vote
0answers
32 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 ...
9
votes
0answers
141 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 ...
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 $\...
7
votes
1answer
156 views

Why does reinforcement learning using a non-linear function approximator diverge when using strongly correlated data as input?

While reading the DQN paper, I found that randomly selecting and learning samples reduced divergence in RL using a non-linear function approximator (e.g a neural network). So, why does Reinforcement ...
1
vote
0answers
21 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 ...
6
votes
1answer
141 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 ...
2
votes
1answer
45 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 ...
2
votes
1answer
55 views

How do we derive the expression for average reward setting in continuing tasks?

In the average reward setting we have: $$r(\pi)\doteq \lim_{h\rightarrow\infty}\frac{1}{h}\sum_{t=1}^{h}\mathbb{E}[R_{t}|S_0,A_{0:t-1}\sim\pi]$$ $$r(\pi)\doteq \lim_{t\rightarrow\infty}\mathbb{E}[R_{t}...
4
votes
2answers
88 views

Why do all states appear identical under the function approximation in the Short Corridor task?

This is the Short Corridor problem taken from the Sutton & Barto book. Here it's written: The problem is difficult because all the states appear identical under the function approximation But ...
5
votes
1answer
1k views

Which machine learning models are universal function approximators?

The universal approximation theorem states that a feed-forward neural network with a single hidden layer containing a finite number of neurons can approximate any continuous function (provided some ...
1
vote
0answers
48 views

Correct dimensionality of parameter vector for solving an MRP with linear function approximation?

I'm in the process of trying to learn more about RL by shadowing a course offered collaboratively by UCL and DeepMind that has been made available to the public. I'm most of the way through the course,...
5
votes
1answer
201 views

Can supervised learning be recast as reinforcement learning problem?

Let's assume that there is a sequence of pairs $(x_i, y_i), (x_{i+1}, y_{i+1}), \dots$ of observations and corresponding labels. Let's also assume that the $x$ is considered as independent variable ...
4
votes
1answer
126 views

What are the differences between artificial neural networks and other function approximators?

Modern artificial neural networks use a lot more functions than just the classic sigmoid, to the point I'm having a hard time really seeing what classifies something as a "neural network" over other ...
4
votes
3answers
132 views

Can we optimize an optimization algorithm?

In this answer to the question Is an optimization algorithm equivalent to a neural network?, the author stated that, in theory, there is some recurrent neural network that implements a given ...
5
votes
3answers
948 views

Which functions can't neural networks learn efficiently?

There are a lot of papers that show that neural networks can approximate a wide variety of functions. However, I can't find papers that show the limitations of NNs. What are the limitations of ...
2
votes
1answer
36 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 \...
7
votes
1answer
86 views

What makes multi-layer neural networks able to perform nonlinear operations?

As I know, a single layer neural network can only do linear operations, but multilayered ones can. Also, I recently learned that finite matrices/tensors, which are used in many neural networks, can ...
2
votes
1answer
73 views

Monte Carlo updates on policy gradient with no terminal state

Consider some MDP with no terminal state. We can apply bootstrapping methods (like TD(0)) to learn in these cases no problem, but in policy gradient algorithms that have only a simple monte carlo ...
3
votes
2answers
107 views

Is there a possibility that there is no relationship between some inputs and outputs?

I'm doing machine learning projects. I took a look at many datasets I worked with, mostly there are already famous datasets that everyone uses. Let's say I decided to make my own dataset. Is there a ...
5
votes
1answer
151 views

Is there a way of converting a neural network to another one that represents the same function?

I have read the paper Neural Turing Machines and the paper On the Computational Power of Neural Nets about the computational power of neural networks. However, it isn't still clear to me one thing. ...
4
votes
1answer
197 views

Convergence of semi-gradient TD(0) with non-linear function approximation

I am looking for a result that shows the convergence of semi-gradient TD(0) algorithm with non-linear function approximation for on-policy prediction. Specifically, the update equation is given by (...