Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.

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
2 votes
0 answers
7 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)$ ...
user avatar
  • 21
0 votes
1 answer
39 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 ...
user avatar
  • 33
0 votes
0 answers
10 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 ...
user avatar
1 vote
0 answers
11 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 ...
user avatar
-1 votes
1 answer
35 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, ...
user avatar
1 vote
0 answers
28 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 ...
user avatar
2 votes
0 answers
62 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 ...
user avatar
0 votes
0 answers
33 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 ...
user avatar
0 votes
0 answers
72 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 ...
user avatar
4 votes
1 answer
56 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 ...
user avatar
1 vote
0 answers
65 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 ...
user avatar
0 votes
0 answers
30 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" ...
user avatar
1 vote
1 answer
55 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 ...
user avatar
  • 746
1 vote
0 answers
37 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 ...
user avatar
  • 3,059
2 votes
1 answer
43 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: ...
user avatar
0 votes
0 answers
42 views

Can reinforcement learning be used to learn an unknown analytical function (for example, $y = x^2$ )?

Are there any examples for RL to learn analytical functions (for example, $y=x^2$)? What are the considerations when constructing the environment? Are there any literature that analyzes the difficulty/...
user avatar
  • 19
1 vote
0 answers
21 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 ...
user avatar
1 vote
0 answers
22 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}...
user avatar
  • 201
2 votes
2 answers
185 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{...
user avatar
  • 33.2k
1 vote
0 answers
40 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 ...
user avatar
  • 3,059
1 vote
2 answers
38 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 ...
user avatar
0 votes
1 answer
101 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 ...
user avatar
-2 votes
1 answer
282 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 ...
user avatar
  • 97
1 vote
2 answers
36 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 ...
user avatar
2 votes
0 answers
32 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 ...
user avatar
  • 121
0 votes
1 answer
85 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$, $\...
user avatar
5 votes
2 answers
759 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. ...
user avatar
1 vote
2 answers
337 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 ...
user avatar
1 vote
0 answers
132 views

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

The code below is adapted from this implementation. ...
user avatar
  • 111
1 vote
0 answers
37 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 ...
user avatar
  • 216
1 vote
0 answers
44 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 ...
user avatar
12 votes
0 answers
261 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 ...
user avatar
  • 663
4 votes
1 answer
71 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 ...
user avatar
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 ...
user avatar
4 votes
1 answer
148 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)...
user avatar
  • 141
6 votes
1 answer
211 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 ...
user avatar
  • 75
2 votes
1 answer
61 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 ...
user avatar
  • 123
3 votes
1 answer
90 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}...
user avatar
4 votes
2 answers
101 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 ...
user avatar
6 votes
1 answer
128 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 ...
user avatar
1 vote
0 answers
55 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,...
user avatar
3 votes
0 answers
697 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. ...
user avatar
4 votes
1 answer
156 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 ...
user avatar
2 votes
1 answer
43 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 \...
user avatar
3 votes
2 answers
121 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 ...
user avatar
  • 213
2 votes
1 answer
90 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 ...
user avatar
2 votes
1 answer
115 views

Which neural network can approximate the function $y = x^2 + b$?

I am new to ANN. I am trying out several 'simple' algorithms to see what ANN can (or cannot) be used for and how. I played around with Conv2d once and had it recognize images successfully. Now I am ...
user avatar
7 votes
1 answer
208 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 ...
user avatar
4 votes
1 answer
309 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 (...
user avatar
1 vote
2 answers
1k views

Why is there a sigmoid function in the hidden layer of a neural network? [duplicate]

I got this slide from CMU's lecture notes. The $x_i$s on the right are inputs and the $w_i$s are weights that get multiplied together then summed up at each hidden layer node. So I'm assuming this is ...
user avatar
  • 351