text:
What is the difference between reinforcement learning and evolutionary algorithms?
What is the difference between reinforcement learning (RL) and evolutionary algorithms (EA)?
I am trying to understand the basics of RL, but I do not yet have practical experience with RL. I know slightly more about EAs, but not enough to understand the difference between RL and EA, and that's why I'm asking for their main differences.

Evolutionary algorithms (EAs) are a family of algorithms inspired by the biological evolution that can be used to solve (constrained or not) optimization problems where the function that needs to be optimized does not necessarily need to be differentiable (or satisfy any strong constraint). In EAs, you typically only need to define

an encoding of the solution (aka chromosome or individual)
a fitness function that determines the relative quality of each solution
operations that stochastically change or combine solutions (e.g. the cross-over or the mutation operators, in genetic algorithms)

There are other parameters that you need to defined (such as the number of solutions to consider at each generation or the number of generations to run the algorithms for), but these are the three most important things to take into account when attempting to solve an optimization problem with EAs (in particular, GAs).
Reinforcement learning (RL) is the field that studies how agents can sequentially take actions in a certain environment in order to maximize some notion of long-term reward (aka return).  The strategy that determines the behavior of the agent (i.e. which actions the agent takes) is called the policy. So, the goal of RL is to find a policy that maximizes the (expected) return, which depends on the reward function of the environment. For example, in the case of chess, a reward function may be any function that gives you a positive number if you win the game or a negative number if you lose it. The RL algorithms typically assume that the agent is able to interact with the environment in order to understand its dynamics.
RL is thus concerned with a specific type of optimization problem, i.e. finding policies (strategies) that maximize the return, while an agent interacts with an environment in time steps. On the other hand, EAs can be applied to any optimization problem where you can encode solutions, define a fitness function that compares solutions and you can stochastically change those solutions. Essentially, EAs can be applied to almost any optimization problem. In principle, you could use EAs to find policies, as long as you're able to compare them with a fitness function (e.g. the amount of reward that you obtain by following these policies).
Of course, this does not mean that EAs are the most efficient and appropriate approach to solve all optimization problems! You typically use EAs when you need to solve certain problems where better approaches do not exist. For example, when your objective function is not differentiable, then you cannot apply gradient-based solutions, so, in that case, EAs may be a viable option (but there are also other alternatives to EAs, such as simulated annealing).


text:
Why is $G_{t+1}$ is replaced with $v_*(S_{t+1})$ in the Bellman optimality equation?
In equation 3.17 of Sutton and Barto's book:
$$q_*(s, a)=\mathbb{E}[R_{t+1} + \gamma v_*(S_{t+1}) \mid S_t = s, A_t = a]$$
$G_{t+1}$ here have been replaced with $v_*(S_{t+1})$, but no reason has been provided for why this step has been taken.
Can someone provide the reasoning behind why $G_{t+1}$ is equal to $v_*(S_{t+1})$?

Can someone provide the reasoning behind why $G_{t+1}$ is equal to $v_*(S_{t+1})$?

The two things are not usually exactly equal, because $G_{t+1}$ is a probability distribution over all possible future returns whilst $v_*(S_{t+1})$ is a probability distribution derived over all possible values of $S_{t+1}$. These will be different distributions much of the time, but their expectations are equal, provided the conditions of the expectation match.
In other words,
$$G_{t+1} \neq v_*(S_{t+1})$$
But
$$\mathbb{E}[G_{t+1}] = \mathbb{E}[v_*(S_{t+1})]$$
. . . when the conditions that apply to the expectations on each side are compatible. The relevant conditions are

Same initial state or state/action at given timestep $t$ (or you could pick any earlier timestep)
Same state progression rules and reward structure (i.e. same MDP)
Same policy

More details
The definition of $v(s)$ can be given as
$$v(s) = \mathbb{E}_\pi[G_t \mid S_t = s]$$
If you substitute step s' and index $t+1$ you get
$$v(s') = \mathbb{E}_\pi[G_{t+1} \mid S_{t+1} = s']$$
(This is the same equation, true by definition, the substitution just shows you how it fits).
In order to put this into equation 3.17, you need to note that:

It is OK to substitute terms inside an expectation if they are equal in separate expections, amd  the conditions $c$ and $Y$ apply to both (or are irrelevant to either one or both). So if for example $\mathbb{E}_c[Z] = \mathbb{E}_c[X \mid Y]$ where $X$ and $Z$ are random variables, and you know $Z$ is independent of $Y$ then you can say $\mathbb{E}_c[W + 2X \mid Y] = \mathbb{E}_c[W + 2Z \mid Y]$ even if $X$ and $Z$ are different distributions.
$A_{t+1} = a'$ does not need to be specified because it is decided by the same $\pi$ in both $q(s,a)$ and $v(s')$, making the conditions on the expectation compatible already. So the condition of following $\pi$ is compatible with $\mathbb{E}_\pi[G_{t+1} \mid S_{t} = s, A_{t}=a] = \mathbb{E}_\pi[v_*(S_{t+1}) \mid S_{t} = s, A_{t}=a]$
The expectation over possible $s'$ in $\mathbb{E}_\pi[v_*(S_{t+1})|S_t=s, A_t=a] = \sum p(s'|s,a)v_*(s')$ is already implied by conditions on the original expectation that the functions are evaluating the same environment - something that is not usually shown in the notation.

Also worth noting, in 3.17 $\pi$ is the optimal policy $\pi^*$, but actually the equation holds for any fixed policy.

Note that for a general policy $\pi$ we have that $q_{\pi}(s,a) = \mathbb{E}_{\pi}[G_t | S_t = s, A_t = a]$, where in state $S_t$ we take action $a$ and thereafter following policy $\pi$. Note that the expectation is taken with respect to the reward transition distribution $\mathbb{P}(R_{t+1} = r, S_{t+1} = s' | A_t = a, S_t = s)$ which I will denote as $p(s',r,|s,a)$.
We can then rewrite the expectation as follows
\begin{align} q_{\pi}(s,a) &= \mathbb{E}_{\pi}[G_t | S_t = s, A_t = a] \\ & = \mathbb{E}_{\pi}[R_{t+1} + \gamma G_{t+1} | S_t = s, A_t = a] \\ & = \sum_{r,s'}p(s',r|s,a)(r + \gamma \mathbb{E}_\pi[G_{t+1} | S_{t+1} = s']) \\ & = \sum_{r,s'}p(s',r|s,a)(r + \gamma v_{\pi}(s')) \; .
\end{align}
The key thing to note is that these two terms, $G_{t+1}$ and $v_{\pi}(s')$, are only equal in expectation, which is why in the equation you can exchange the terms because we are taking the expectation.
Note that I have shown this for a general policy $\pi$ not just the optimal policy.

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

sort: votes


text:
What should the action space for the card game Crib be?
I'm working on creating an environment for a card game, which the agent chooses to discard certain cards in the first phase of the game, and uses the remaining cards to play with. (The game is Crib if you are familiar with it.)
How can I make an action space for these actions? For instance, in this game, we could discard 2 of 6 cards, then choose 1 of 4 remaining cards to play, then 1 of 3 remaining cards, then 1 of 2 remaining cards. How do I model this?
I've read this post on using MultiDiscrete spaces, but I'm not sure how to define this space based on the previous chosen action. Is this even the right approach to be taking?

I am not familiar with the game, but the way it looks - you are performing only one action - which is discarding cards. The only thing that changes is the number of times you are performing that action.

I've actually implemented this game before using deep reinforcement learning. You are dealing with a dynamic action space here, where the action space may change at each time step of the game (or more generally the MDP). First, let's discuss the actual action spaces in each one of the two phases of Crib (or Cribbage) and formalize the question.
Phase 1: The Discard:In this phase, you are concurrently discarding  2 cards without respect to order. Therefore, you have a fixed discrete action space of size ${{6}\choose{2}} = 15$.
Phase 2: The Play: In this phase, you and your opponent are sequentially playing one of each of your remaining 4 cards (the original 6 minus the 2 discarded from phase 1). Therefore, you have a discrete action space of size $4! = 24$. Here's the catch - not every one of these actions is legal. The current state of the game restricts which cards you are allowed to play (the sum of all cards currently played must not be greater than 31). Since you do not know your opponent's cards and/or policy, you do not know which of these 24 actions are valid. To remedy this, the action space should dictate which of your remaining cards may be played at the current time step. Thus, you have a dynamic discrete action space of size 1, 2, 3, or 4 at each time step.

How can I make an action space for these actions?

Since you didn't specify any implementation standard (e.g. OpenAI Gym), there are multiple paths to take, and they usually depend on your implementation of the state feature vector. In my own implementation, I tinkered with two possible state representations, which are fairly simple to describe.
Possibility 1: Separate State Representations for each Phase: In phase 1, you need to know the cards in your hand and the scores; i.e., the state feature vector could be encoded as a list of [card0, card1, card2, card3, card4, card5, your score, opponent score]. This state represents all information known about the game during phase 1 from a single player's viewpoint; after each time step, the current player may change, and the state must be updated according to the current player's viewpoint. Each card can be encoded as an integer from 1 to 52 (not starting from 0, as we will see in the next paragraph), and the score is an integer from 0 to 120 (tip: sort your cards for a reduced state space and faster convergence). Your action space can be the set of integers from 0 to 14 that maps to a 2-card combination in your hand. Alternatively, you could have a dynamic action space that sequentially asks for 1 of your 6 cards to discard and then for 1 of your remaining 5 cards to discard. The action space can be a subset of integers from 0 to 5 that maps to a single card in your hand. Be careful here - when choosing the second card to discard, your algorithm must know which card was discarded first. You can solve this by adding another component to your state vector that represents the first card that was discarded (set to 0 at the beginning of the phase), and therefore, make sure to update the state after the first discard.
In phase 2, you need to know the 4 cards in your hand, the cut card, the scores, and the cards currently played. Another helpful but unnecessary feature for learning is the current sum of played cards. A possible representation is a list of [card0, card1, card2, card3, card played0, card played 1, card played 2, …,  card played 7, your score, opponent score, cut card, current sum of played cards]. The values of played cards should be initialized to 0 at the beginning of the phase. The state can be updated so that any card in your hand that you have played is set to 0, and any card played by your opponent can be set to its negative value. This will correctly encode which cards have been played from your hand, which cards played are your from your opponent, and all other available information. Consequently, the action space is dynamic and is a subset of integers from 0 to 3 that maps to a single card in your hand.
Possibility 2: Identical State Representations for each Phase Another possibility is to have all of the above information for each phase encoded into a single state representation along with the phase number. State features that are unique to phase 2 that aren't relevant for phase 1 can be set to 0 during phase 1 and vice versa. With this representation, the state feature vector is of the same length at all time steps of the game, and the action space will change as described above. The important ideas for the encoding are exactly the same as above and will change based on your particular implementation, so I won't include the details here.

How do I model this?

If you are going to implement something similar to Possibility 1, then you may need two agents that each learn a policy for a separate phase. For starters, you could use Q-learning or DQN and take the action with greatest q-value at each timestep, making sure that the chosen action is always a member of the current action space.
If you are going to implement something similar to Possibility 2, then you may only need a single agent that learns a policy for each phase, simply because the phase is a feature of the state. Essentially you are trading off a more complicated state representation for a simpler learning algorithm.

I've read this post on using MultiDiscrete spaces, but I'm not sure how to define this space based on the previous chosen action. Is this even the right approach to be taking?

After reading the OpenAI Gym documentation, it looks like the MultiDiscrete space is a product of Discrete spaces. Therefore, it is a fixed action space and inherently not what you want here (a dynamic action space). I don't believe that OpenAI Gym standards will support dynamic action spaces natively. You would need to do some extra work such as providing a method that returns the current action space of the environment. Alternatively, if you want to follow the (state, reward, done, info) signal paradigm from OpenAI Gym, you may provide the current action space in the info dictionary. Finally, another idea is to allow the agent to always choose an action from a larger fixed action space (e.g. the set of integers from 0 to 3 for phase 2) and then penalize the agent through the reward signal whenever it chooses an action that is not a member of the current action space (e.g. if the chosen card was already played in phase 2). Afterward, you would return the current game state as the next state and make the agent try again.
My advice is to first determine the state representation, and the rest of your implementation should follow, using the ideas above.

Wow, thanks for your reply, It really helps me out a lot! I am using OpenAI Gym, so this information is very actionable for me. It looks like this is exactly what I'm after so I'll try to implement one of your suggestions.

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
How is the formula for the Bayes error rate with an integral derived?
My questions concern a particular formulation of the Bayes error rate from Wikipedia, summarized below.

For a multiclass classifier, the Bayes error rate may be calculated as follows: $$p = 1 - \sum_{C_i \ne C_{\max,x}} \int_{x \in H_i} P(C_i|x)p(x)\,dx$$ where $x$ is an instance, $C_i$ is a class into which an instance is classified, $H_i$ is the area/region that a classifier function $h$ classifies as $C_i$.

We are interested in the probability of misclassifying an instance, so we wish to sum up the probability of each unlikely class label (hence we want to look at $C_i \ne C_{\max, x}$).
However, the integral is confusing me. We want to integrate an area corresponding to the probability that we choose label $C_i$ given $x$. But we drew $x$ from $H_i$, the region covered/classified by $C_i$, so wouldn't $P(C_i|x) = 1$?
I think most of my confusion will be resolved if someone can help clarify the intention of the integral.
Is it to draw random samples from the total space of $h$ (the classifier function), and then sum the probabilities from each classified $C_i \ne C_{\max, x}$? How does $x$ exist in the outer summation before it has been sampled from $H_i$ in the integral?

Bayes Error Rate
For the general case of K different classes, the probability of classifing x instance correctly is:
\begin{equation} \label{eq1}
\begin{split}
P(correct) & = \sum_{i=1}^{K} p(x \in H_i, C_i) \\
 & = \sum_{i=1}^{K} \int_{x \in H_i} p(x,C_i) \, dx\\
 & = \sum_{i=1}^{K} \int_{x \in H_i} P(C_i|x)p(x)\,dx \\
\end{split}
\end{equation}
where $H_i$ is the region where class $i$ has the highest posterior. So the Bayes Error Rate is:
\begin{equation} \label{eq2}
\begin{split}
P(error) & = 1 - p(correct) \\
 & = 1 - \sum_{i=1}^{K} \int_{x \in H_i} P(C_i|x)p(x)\,dx
\end{split}
\end{equation}
Be careful if we drew $x$ from $H_i$, the region covered/classified by $C_i$, $P(C_i|x) \ne 1$, because that would mean that we surely predict correctly all the time. If $x$ belongs to a decision area, this does not imply that it belongs to the corresponding class.

Ah, I think I get it now. We are looking at the region $H_i$ and integrating the probability that our $x$ would occur (given class $C_i$) over the entire region. Does that sound correct?


text:
How to avoid rapid actuator movements in favor of smooth movements in a continuous space and action space problem?
I'm working on a continuous state / continuous action controller. It shall control a certain roll angle of an aircraft by issuing the correct aileron commands (in $[-1, 1]$).
To this end, I use a neural network and the DDPG algorithm, which shows promising results after about 20 minutes of training.
I stripped down the presented state to the model to only the roll angle and the angular velocity, so that the neural network is not overwhelmed by state inputs.
So it's a 2 input / 1 output model to perform the control task.
In test runs, it looks mostly good, but sometimes, the controller starts thrashing, i.e. it outputs flittering commands, like in a very fast bangbang-controlm which causes a rapid movement of the elevator.

Even though this behavior kind of maintains the desired target value, this behavior is absolutely undesirable. Instead, it should keep the output smooth. So far, I was not able to detect any special disturbance that starts this behavior. Yet it comes out of the blue.
Does anybody have an idea or a hint (maybe a paper reference) on how to incorporate some element (maybe reward shaping during the training) to avoid such behavior? How to avoid rapid actuator movements in favor of smooth movements?
I tried to include the last action in the presented state and add a punishment component in my reward, but this did not really help. So obviously, I do something wrong.

Try applying first order filter on the output. That should smooth out the control signal

This should definitively work. It's kind of the engineering approach and I think I'll try that. However, there should be a way to prevent the agent from learning such behavior. So, good ideas are still welcome.

Btw, are you learning through entire trajectory? Idk if you're familiar with adaptive control, but there, if you do online parameter estimation, you need persistent excitation, otherwise estimation problem becomes singular and model estimate drifts off. Similar thing might happen here where network keeps getting same learning examples of steady state and it 'forgets' how to control the system. You might try adding disturbance signal every now and then to excite dynamics so that experience replay has variety of different examples or you could stop learning through entire steady state.

After some research on the subject, I found a possible solution to my problem of high frequency oscillations in continuous control using DDPG:
I added a reward component based on the actuator movement, i. e. the delta of actions from one step to the next.
Excessive action changes are punished now and this could mitigate the tendency to oscillate. The solution is nnot really perfect, but it works for the moment.
This finding is detailed out in the "Reward Engineering" section of my master's thesis. Please have a look into https://github.com/opt12/Markov-Pilot/tree/master/thesis
I'll be glad to get feedback on it. And I'll be glad to hear better solutions than adding a delta-punishment.
Regards, Felix


text:
Should I use minimax or alpha-beta pruning?
Should I use minimax or alpha-beta pruning (or both)? Apparently, alpha-beta pruning prunes some parts of the search tree.

Both algorithms should give the same answer. However, their main difference is that alpha-beta does not explore all paths, like minimax does, but prunes those that are guaranteed not to be an optimal state for the current player, that is max or min. So, alpha-beta is a better implementation of minimax.
Here are the time complexities of both algorithms

Minimax: $\mathcal{O}(b^d)$,
Alpha-beta (best-case scenario): $\mathcal{O}(b^{d/2})  = \mathcal{O}(\sqrt{b^d})$

where $b$ is an average branching factor with a search depth of $d$ plies.

Minimax is the base algorithm, and alpha beta pruning is an optimisation that you can apply to minimax to make it more efficient.


text:
How is $\Delta$ updated in true online TD($\lambda$)?
In the RL textbook by Sutton & Barto section 7.4, the author talked about the "True online TD($\lambda$)". The figure (7.10 in the book) below shows the algorithm.
At the end of each step, $V_{old} \leftarrow V(S')$ and also $S \leftarrow S'$. When we jump to next step, $\Delta \leftarrow V(S') - V(S')$, which is 0. It seems that $\Delta$ is always going to be 0 after step 1. If that is true, it does not make any sense to me. Can you please elaborate on how  $\Delta$ is updated?

Let us denote the state we are in at time $t$ by $S_t$. Then at iteration $t$ we create a placeholder $V_{old} = V(S_{t+1})$ for the state we will transition into. We then update the value function $V(s) \; \forall s \in \mathcal{S}$ - i.e. we update the value function for all states in our state space. Let us denote this updated value function by $V'(S)$.
At iteration $t+1$ we calculate $\Delta = V'(S_{t+1}) - V_{old} = V'(S_{t+1}) - V(S_{t+1})$, which does not necessarily equal 0 because the placeholder $V_{old}$ was created using the value function before the last update.

Ah, I see! I missed the fact that when TD updates, it updates the whole state space! Thank you so much, David!


text:
Why not replacing the simple linear functions that neurons compute with more complex functions?
In a neural network, a neuron typically computes a linear function $f(x) = w*x$, where $w$ is the weight and $x$ is the input.
Why not replacing the linear function with more complex functions, such as $f(x,w,a,b,c) = w*(x + b)^a + c$?
It will provide much more diversity into neural networks.
Does this have a name? Has this been used?

In your previous version of this post, you were using the word "weight" as if it was a function, but it's not. The weight is a number. The neuron computes some function. I think it's important you differentiate the two! So, it's the neuron that can compute more complex functions and "not the weight that can compute more complex functions".

It is definitley possible to make the links between neurons use more complex functions. Provided those functions are differentiable, backpropagation still works, and the resulting compound function might be able to learn something useful. The general name for such a thing is a computational graph and the standardised structures used in most neural networks are a subset of all possible (and maybe useful) computational graphs.
When adding complex and non-linear functions into a neural network, this is usually alternated with simpler linear layers using the weights. A generalised function of a single neuron as used in most neural networks looks like this:
$$a = f(\sum_i w_i x_i + b)$$
Where $i$ indexes all inputs to the neuron, $x_i$ are the input values, $w_i$ the weights associated with each input, $b$ is a bias term and $f()$ is a differentiable non-linear activation function. Training process learns $w_i$ and $b$. The output $a$ is the the neuron's activation value, that may be taken as output of the neural network, or fed in to some other neuron as one of the next neuron's $x_i$.
A simple feed-forward network using this basic neuron function, with at least one hidden layer which has a non-linear activation function can already learn approximations to any given function - a result proved in the universal approximation theorem.
The practical result of the universal approximation theorem is that you need motivation other than increasing diversity in order to make neural network functions more complex. If you were considering altering one of the $w_i x_i$ multiplications, and replacing with a more complex learnable function, you can effectively achieve the same thing by adding another neuron whose output $a$ is used as $x_i$ - or simply adding a layer in most neural network libraries.
In some situations there may be good reasons to make lower-level changes:

If you know the function you are learning relates to a theoretical model with a specific mathematical form, you can deliberately set up functions that mirror that with learnable parameters. Typcially that is done as transforms on inputs, but could also be part of a more complex computational graph if necessary.
In neural network architectures, you can consider things such as gate combinations in LSTM cells, or skip connections in residual networks as examples where the functions have deliberately be made more complex to achieve a specific goal - in both those cases in order to increase effectiveness of backpropagation in deep structures.

authors: Григорий Маклаков


text:
Are there other mathematical frameworks of artificial general intelligence apart from AIXI?
AIXI is a mathematical framework for artificial general intelligence developed by Marcus Hutter since the year 2000. It's based on many concepts, such as reinforcement learning, Bayesian statistics, Occam's razor, or Solomonoff induction. The blog post What is AIXI? — An Introduction to General Reinforcement Learning provides an accessible overview of the topic for those of you not familiar with it.
Are there any other mathematical frameworks of artificial general intelligence apart from AIXI?
I am aware of projects such as OpenCog, but that's not really a mathematical framework, but more a cognitive science framework.

Gödel machine
There is another mathematical framework for AGI: the Gödel machine, which was proposed by Jürgen Schmidhuber (who also worked with Marcus Hutter). In the paper Gödel Machines: Self-Referential Universal Problem Solvers Making Provably Optimal Self-Improvements (2003), Schmidhuber describes the Gödel machine as follows

They are universal problem solving systems that interact with some (partially observable) environment and can in principle modify themselves without essential limits apart from the limits of computability. Their initial algorithm is not hardwired; it can completely rewrite itself, but only if a proof searcher embedded within the initial algorithm can first prove that the rewrite is useful, given a formalized utility function reflecting computation time and expected future success (e.g., rewards). We will see that self-rewrites due to this approach are actually globally optimal (Theorem 4.1, Section 4), relative to Gödel's well-known fundamental restrictions of provability. These restrictions should not worry us; if there is no proof of some self-rewrite's utility, then humans cannot do much either.
The initial proof searcher is $O$()-optimal (has an optimal order of complexity) in the sense of Theorem 5.1, Section 5. Unlike hardwired systems such as Hutter's and Levin's (Section 6.4), however, a Gödel machine can in principle speed up any part of its initial software, including its proof searcher, to meet arbitrary formalizable notions of optimality beyond those expressible in the $O$()-notation. Our approach yields the first theoretically sound, fully self-referential, optimal, general problem solvers.

Space-time embedded agents
This work combines Russell's bounded rationality with Legg's and Hutter's definition of universal intelligence to provide a framework for AGI that takes into account resource (space and time) constraints and other issues (such as that the environment can modify or even destroy the agent).


text:
Is there a way of deriving a loss function given the neural network and training data?
There is some sort of art to using the right loss function. However, I was wondering if there is a way to derive the loss function if I gave you a neural network model (the weights) as well as the training data.
The point of this exercise is to see what family of loss functions we would get. And how that compares to the loss function that actually gave rise to the model.

I don't think there's a way of doing what you want, at least, I've never seen such a thing (and, currently, I am not seeing how this could be done in the general case).
The same neural network model but with different (or same) weights could have been trained with the same loss function or not. For example, although it may not be a good idea, you can train a neural network for classification with the mean squared error, as opposed to the typical cross-entropy. Moreover, even if you know the loss function that the neural network is trained with, the training data alone may not lead to the same set of weights because the actual weights depend on different (possibly stochastic) factors, such as if (or how) you shuffle the data or the batch size.

I deleted my comment as soon as I read it / it was poorly expressed and you are too fast. I realize that I neglected the architecture of the network as well

The idea that led me to this question is the fact that any function can be represented as a polynomial approximation (Taylor series for example). Since the loss function is thus represented, then maybe the tools of linear algebra can be used to derive it from the weights of a model and the training data. Having such a loss function should then allow training the original network from the training data from a single densely connected layer.

@aquagremlin I see your point. I am not excluding the possibility to do something in that direction, but, right now, I am not seeing a solution.

Why bother to make a loss function like this? Because I want to see if it converges faster to a smaller error. And although derived from a specific set of weights and training data, it might be applicable to similar desired models -for example instead of having a single complicated network to recognize faces, we might have several simpler single layer networks for different parts of the world. These models would smaller, faster and deployable and smaller cheaper hardware

@aquagremlin When I was writing this answer, I found some papers that introduce a way of learning a loss function. For example, see the paper Learning to Teach with Dynamic Loss Function.


text:
What is the effect of using pooling layers in CNNs?
I know how pooling works, and what effect it has on the input dimensions - but I'm not sure why it's done in the first place. It'd be great if someone could provide some intuition behind it - while explaining the following excerpt from a blog:

A problem with the output feature maps is that they are sensitive to the location of the features in the input. One approach to address this sensitivity is to down sample the feature maps. This has the effect of making the resulting down sampled feature maps more robust to changes in the position of the feature in the image, referred to by the technical phrase “local translation invariance.”

What's local translation invariance here?

Pooling has multiple benefits

Robust feature detection.
Makes it computationally feasible to have deeper CNNs

Robust Feature Detection
Think of max-pooling (most popular) for understanding this.
 Consider a 2*2 box/unit in one layer which is mapped to only 1 box/unit in the next layer (Basically pooling). Let's say the feature map (kernel) detects a petal of a flower. Then qualifying a petal if any of the 4 units of the previous layer is fired makes the detection robust to noise. There is no strict requirement that all 4 units should be fired to detect a petal. Thus, the next layer (after pooling) captures the features with noise invariance. We can also say it is local translation invariance (in a close spatial sense) as a shifted feature will also be captured. But also remember translation invariance in general is captured by the convolution with kernels in the first place. (See how 1 kernel is convolved with the whole image)
Computational advantage
The dimensions of the inputs in image classification are so huge that the number of the multiplication operation is in billions even with very few layers. Pooling the output layer reduces the input dimension for the next layer thus saving computation. But also now one can aim for really deep networks(number of layers) with the same complexity as before.

In addition in general it somewhat aides in detection as only the strongest feature feature filter is activated so in a sense it removes additional information.
But it obviously has draw backs resulting in combinations of features being detected which aren't actual.objects.


text:
If deep Q-learning starts to choose only one action, is this a sign that the algorithm diverged?
I'm working on a deep q-learning model in an infinite horizon problem, with a continous state space and 3 possible actions. I'm using a neural network to approximate the action-value function. Sometimes it happens that, after a few steps, the algorithm starts choosing only one between the possible actions (apart from a few steps where I suppose it explores, given the epsilon-greedy policy it follows), leading to bad results in terms of cumulative rewards. Is this a sign that the algorithm diverged?

Is this a sign that the algorithm diverged?

It is a common sign of a problem with learning process. That includes divergence due to poor hyper-parameters, even just bad luck. But it can also point to a design/architecture problem.
Other common causes of algorithm failing with a fixed action choice include:

Neural network inputs not scaled before use.
Large reward values causing large initial squared errors (either re-scale rewards or reduce learning rate to fix)
State representation too far from Markov property assumption
A bug in code (almost anywhere, unfortunately)
Catastrophic forgetting due to focusing too much on specific results and generalising from them incorrectly. Your agent might be suffering from this if it starts to learn correctly, reaching some level of competence at the task before failing.

I'm in the "deadly triad" case, so it is not such a surprise that it can easily diverge. I still have to try more sophisticated reward functions so I hope that I can soft that tendency in this way.


text:
Is the distribution of state-action pairs from sample based planning accurate for small experience sets?
From the David Silver's lecture 8: Integrating Learning and Planning - based on Sutton and Barto - he talks about using sample-based planning to use our model to take a sample of a state and then use model-free planning, such as Monte Carlo, etc, to run the trajectory and observe the reward. He goes on to say that this effectively gives us infinite data from only a few actual experiences.
However, if we only experience a handful of true state-action-rewards and then start sampling to learn more then we will surely end up with a skewed result, e.g., If I have 5 experiences but then create 10000 samples (as he says, infinite data). I am aware that as the experience set grows the Central Limit Theorem will come into play and the distribution of experience will more accurately represent the true environment's state-actions-rewards distribution but before this happens is sampled based planning still useful?

I am aware that as the experience set grows the Central Limit Theorem
  will come into play and the distribution of experience will more
  accurately represent the true environment's state-actions-rewards
  distribution

I believe here you mean the Law of Large Numbers which states that for a large enough sample ($n \rightarrow \infty$) the sample mean will converge to the true mean. The central limit theorem (CLT) states that if you take the sum/mean of a set of independent random variables then the distribution of this new RV will be approximately normal as $n \rightarrow \infty$.

before this happens is sampled based planning still useful

As you mentioned, if you had only 5 full episodes of experience to choose from, then this likely would not represent true underlying distributions and so the approximations would not be good -- of course, this will depend on how complex your MDP is, if you had a trivially simple one then it may be enough to represent it well. As David Silver says in his lecture, then one of the disadvantages of planning with a model is that you introduce another set of uncertainty, mainly from when you approximate the properties of the model.

Much appreciated. I did mean the Law of Large Numbers, thanks for the correction.
So it all seems a trade-off between MDP complexity and the size of experience set.

yes, as you are just learning the model through supervised learning methods, the same rules apply i.e. the complexity of your problem will determine how much data you need to balance the bias/variance trade off


text:
What is the intuition behind the Xavier initialization for deep neural networks?

The aim of weight initialization is to prevent layer activation outputs from exploding or vanishing during the course of a forward pass through a deep neural network

I am really having trouble understanding weights initialization technique and Xavier Initialization for deep neural networks (DNNs).
In simple words (and maybe with an example), what is the intuition behind the Xavier initialization for DNNs? When should we use Xavier's initialization?

An excellent explanation is available at https://towardsdatascience.com/weight-initialization-in-neural-networks-a-journey-from-the-basics-to-kaiming-954fb9b47c79

Weight initialization is one of the most critical factors for successfully training a deep neural network. This explanation by deeplearning.ai is probably the best that one could give for the need for initializing a DNN with Xavier initialization. Here is what it talks about in a nutshell:
The problem of exploding and vanishing gradients has been long-standing in the DL community. Initialize all the weights as zeros and the model learns identical features across all hidden layers, initialize random but large weights and the backpropagated gradients explode, initialize random but small weights and gradients vanish. The intuition is aptly captured by this simple mathematical observation: $1.1^{50} = 117.390$, while at the same time, $0.9^{50} = 0.00515$. Note that the difference between the two numbers is just $0.1$ but it has a tremendous effect when multiplied repeatedly! A typical NN is a series of function compositions involving weight matrices and linear/non-linear activation functions. When stripped to a bare minimum, it essentially is a series of matrix multiplications. Therefore, the way in which the elements of these weight matrices are initialized plays a major role in how the network learns.
The standard weight initialization methods come into the picture here. They reinforce what are the de-facto rules of thumb when it comes to weight initializations: (1) the mean of the activations should be zero, and (2) the variance of these activations across all the layers should be the same.
Note: The link given above has complete mathematical justification for why Xavier initialization works, along with an interactive visualization for the same.

But even with Xavier initialization we can have vanishing gradients. For example in a FC with 10 layers and 1 neuron per layer, each neuron will be initialized from $\mathcal{N} (0, 1)$. These numbers can still be small, and as such their product $0.5^{10}$ can also be small.


text:
Can tabular Q-learning converge even if it doesn't explore all state-action pairs?
My understanding of tabular Q-learning is that it essentially builds a dictionary of state-action pairs, so as to maximize the Markovian (i.e., step-wise, history-agnostic?) reward. This incremental update of the Q-table can be done by a trade-off exploration and exploitation, but the fact remains that one "walks around" the table until it converges to optimality.
But what if we haven't "walked around" the whole table? Can the algorithm still perform well in those out-of-sample state-action pairs?

I removed the part about the "self-learned algorithm" or "self-learning", which are ambiguous terms, in order to avoid more discussions in this comment section. If you have a question related to the term "self-learning", you can ask it as a separate question. Similarly, if you have a question about whether Q-learning is really a learning algorithm or not, ask it as another separate question.

@nbro Thanks. I don't have enough command in this field to rephrase what I meant by "self-learning". If I did, I might not have asked the question in the first place. I think that most people can get the gist of what I meant and meet me half-way in understanding the question. As I had mentioned, tabular Q-learning seems to me to be more akin to a parameter-sweep or a grid search than  that can extrapolate to unseen data. It's this very aspect which I'd like to clear up.

If you wonder if Q-learning can generalize to unseen environments, the answer is probably no, unless you train the network on the unseen environment again, but does this imply that it's not a learning algorithm? Note that learning can be thought of as a search. There are some questions on this site related to the topic, if you are interested.

In the tabular case, then the Q table will only converge if you have walked around the whole of the table. Note that to guarantee convergence we need $\sum\limits_{n=1}^{\infty}\alpha_n(a) = \infty$ and $\sum\limits_{n=1}^\infty \alpha_n^2(a) < \infty$. These conditions imply that in the limit each state-action pair will have been visited an infinite number of times, thus we will have walked around the whole table, so there are no out-of-sample state-action pairs.
However, in the case of function approximation, then convergence is no longer guaranteed. Generalisability is possible though - assuming we have an infinite state or action space then we will only ever visit the same state-action pair once, so the role of a function approximator is to allow us to generalise the state/action space.
NB that the convergence conditions I mentioned are only required in some proofs of convergence, depending on what type of convergence you are looking to prove. See this answer for more details.

My initial question (which has now been edited by an admin) was  really about whether tabular Q-learning is just a search-based algorithm or one that actually can predict out of sample. I gather from your answer that it is search-based whereas functional methods---presumably such as DQN?--- can predict out of sample?

in tabular Q-Learning there isn't such a thing as 'out of sample'. As I said, in the limit, you will have explored every state-action pair of the MDP. If you introduced a new state-action pair not originally defined in the MDP then you would have to run Q-Learning on this new MDP as it is a new problem. In functional methods it is inherently out of sample because even in the limit you would not visit any state more than once (or even visit every state), so it has to generalise to unseen states, but the states are still defined per the MDP.


text:
What is a RAM state in the gym's breakout-ram environment?
I have encountered the gym environment and decided to create AI that plays breakout. Here is the link: https://gym.openai.com/envs/Breakout-ram-v0/.
The documentation says that the state is represented as a RAM state, but what is the RAM in this context? Is it the random access memory? What does the RAM state represent?

Yes, it is the state of the memory; this would mainly involve variables, since the code would be in ROM. Since it is only 128 bytes in size, the screen memory would also not be included in this.
The idea is that all information relevant to the game is captured in these 128 bytes; they represent the state of the game world at any given time. Movements of the ball, the game controller position, etc are all encoded there.
For machine learning it is not actually relevant which bytes are representing which value, as any optimisation of outcomes will treat all these 128 bytes as parameters describing the state. A machine learning system will pick up the optimal configuration through the learning process, eg that the 'racket' position should always near the ball x-coordinate. That will just be a correlation of two bytes, no matter which ones they actually are.

and what does this information represents?what state of memory i don't understand this term at all, please help me

if you were given array of 128 numbers and told to build neural network, isn't it important what these 128 numbers represents?it's very abstract to me.

@datonefaridze see update


text:
Can the agent wait until the end of the episode to determine the reward in SARSA?
From Sutton and Barto's book Reinforcement Learning (Adaptive Computation and Machine Learning series) (p. 99), the following definition for first-visit MC prediction, for estimating $V \sim V_\pi$ is given:

Is determining the reward for each action a requirement of SARSA? Can the agent wait until the end of the episode to determine the reward?
For example, the reward for the game tic-tac-toe is decided at the end of the episode, when the player wins, loses, or draws the match. The reward is not available at each step $t$.
Does this mean then that depending on the task it is not always possible to determine reward at time step $t$, and the agent must wait until the end of an episode? If the agent does not evaluate reward until the end of an episode, is the algorithm still SARSA?

There are a couple of things to break down here.
The first thing is to correct this:

For example, the reward for the game tic-tac-toe is decided at the end of the episode, when the player wins, loses, or draws the match. The reward is not available at each step $t$.

In a Markov Decision Process (MDP), there is always an immediate reward for each time $t$ from $t=1$ to $t=T$ (terminal state). This is the reward distribution that the algorithms refer to as $R_t$.
It does not matter if nearly all the rewards are $0$. That is still a reward value, even if it is not an interesting or informative one. Some environments will have non-zero rewards on nearly all time steps. Some environments might have zero rewards for every transition apart from one or two important exceptions that define the goal of the agent.
So in tic-tac-toe, if the game has not ended, the reward will be $0$ because neither player has won or lost, and obtaining a win is a learning objective. If you use $0$ reward value for all incomplete time steps in tic-tac-toe, and SARSA algorithm as written from Sutton & Barto, then it will work as expected. You don't need to wait until the end of the episode, and the algorithm will still learn to predict values of moves despite experiencing many $r_t = 0$ during start and middle of the game.
You show the MC prediction algorithm, which does wait until the end of each episode until calculating estimated values, using the experienced return.
I think one of the things that you might want to review is the difference between immediate reward following a timestep (noted $R_{t+1}$) and return (noted $G_t$). There is a relationship between the two $G_t = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}$. All the value based methods, such as MC prediction, or SARSA, are ways to estimate the expected return $\mathbb{E}_{\pi}[G_t]$ given some context, such as the state or state and action at time $t$.
Given that, this should answer your other questions.

Is determining the reward for each action a requirement of SARSA?

It is a general requirement for MDPs, and is expected by all solvers. However, a default of $0$ is fine, if that's how the environment works. The reinforcement learning (RL) algorithms can all cope with delays to important reward values (such as those from winning or losing a game). Bigger delays - e.g. thousands of $0$ reward steps between more meaningful values - are often associated with harder problems to solve, so the simpler algorithms might not be practical. But they all cope in theory given enough experience.

Can the agent wait until the end of the episode to determine the reward?

No, you should always be able calulate an immediate reward value $r_{t+1}$ after taking each action $a_t$ from state $s_t$.
However, it is OK in general to wait until you have summed up more of those rewards (e.g. $r_{t+1}$ to $r_{t+n}$) before making an estimate of the return $g_t$ to update a value estimate. Single step SARSA (sometimes called SARSA(0)) does not wait - it makes update steps using a single immediate reward value. However, other agent types including Monte Carlo (MC), and some variants of SARSA, can and do wait - sometimes just for some steps, sometimes until the end of each episode.
It is a choice you can make when designing agents, there are consequences. Waiting until end of the episode (as in MC) means you have unbiased estimates of value, but takes longer, and leads to higher variability in updates. Using reward values after each step (as in SARSA(0)) means you get to make more frequent updates which may converge fatser, but you start with biased incorrect values.


text:
Into which subcategories can reinforcement learning be divided?
In the course of a scientific work, I will discuss the different types of reinforcement learning. However, I have difficulties to find these different types.
So, into which subcategories can reinforcement learning be divided? For example, the following subdivisions seem to be useful

Model-free and Model-based
Dynamic Programming, Monte Carlo and Temporal Difference

Any others?

Your two suggestions are not mutually exclusive. If you go by this process, you'll have to do a "Cartesian product" of a bunch of different RL categorizations which would get out of hand. I recommend, if you can, to describe some sort of "RL taxonomy" instead. By this I mean describing different RL characterizations without assuming they're mutually exclusive.
To add to your list :

On-policy or off-policy
Value based or policy gradient

Maybe you could include a diagram like this one. It's your choice, but sometimes diagrams help.

+1 for the diagram nbro posted, that's a great visualization for what I was trying to describe


text:
Is it possible to apply the associative property of the convolution operation when it is followed by a non-linearity?
The associative property of multidimensional discrete convolution says that:
$$Y=(x \circledast h_1) \circledast h_2=x\circledast(h_1\circledast h_2)$$
where $h_1$ and $h_2$ are the filters and $x$ is the input.
I was able to do exploit this property in Keras with Conv2D: first, I convolve $h_1$ and $h_2$, then I convolve the result with $x$ (i.e. the rightmost part of the equation above).
Up to this point, I don't have any problem, and I also understand that convolution is linear.
The problem is when two Conv2D layers have a non-linear activation function after the convolution. For example, consider the following two operations
$$Y_1=\text{ReLU}(x \circledast h_1)$$
$$Y_2=\text{ReLU}(Y_1\circledast h_2)$$
It is possible to apply the associative property if the first or both layers have a non-linear activation function (in the case above ReLU, but it could be any activation function)? I don't think so. Any idea or related paper or some kind of approach?

Yes, when you have non-linearity it is not possible to combine your convolution steps.
However, you can approximate the two layers network with one layer net according to the Universal Approximation Theorem. You will probably need to use something like a knowledge distillation technique to do it. Note that, the theorem doesn't say anything about the number of neurons required or if the learning techniques that we usually use will work well.
Also, $ReLU(x)$ is a linear mapping when $x \geq 0$, so if your input, weight, and biases are $\geq 0$, the net can be exactly modeled with a single layer network.

Thx! I will investigate about "Universal Approximation Theorem", I've never heard. I am trying to optimize cascade convolutions as much as possible since I am implementing convolutional neural networks in an electronic device.


text:
A neural network with 2 or more hidden layers is a DNN?
I just learned the math behind neural networks so please bear with my ignorance. I wonder if there is a precise definition for DNN.
Is it true that any neural network with more than 2 hidden layers can be named as a DNN, and training a NN with 2 hidden layers using Q-learning we are technically doing a type of deep reinforcement learning?
PS: If it is conceptually that simple why do common people regard deep learning as something done by archmages in ivory towers.

I don't think there is a fixed threshold that differentiates between Shallow and Deep Learning, but I would say that a 2 layer NN should not be considered deep. But now-a-days, almost all NN architectures are studied under the umbrella of Deep Learning.
And yes, training a 2 hidden layers NN using Q-learning would technically mean doing deep RL.
I guess it is conceptually simple but making NN perform optimally is an art. Tuning hyperparameters or debugging NN can be tough and one learns with experience. I guess others in the community would be much more suited to answer this question. But these were my 2 cents.


text:
Which heuristics guarantee the optimality of A*?
The following is a statement and I am trying to figure out if it's true or false and why.

Given a non-admissible heuristic function, A* will always give a solution if one exists, but there is no guarantee it will be optimal.

I know that a non-admissible function is $h(n) > h^*(n)$ (where $h^*(n)$ is the real cost to the goal), but I do not know if there is a guarantee.
Which heuristics guarantee the optimality of A*? Is the admissibility of the heuristic always a necessary condition for A* to produce an optimal solution?

Given a non-admissible heuristic function, A* will always give a solution if one exists, but there is no guarantee it will be optimal.

I won't duplicate the proof here, but it isn't too hard to prove that any best-first search will find a solution for any measure of best, given that a path to the solution exists and infinite memory. A* is a best-first search algorithm, so it will always find a solution if one exists.

Which heuristics guarantee the optimality of A*? Is the admissibility of the heuristic always a necessary condition for A* to produce an optimal solution?

Admissibility is not a necessary condition. Take any admissible heuristic $h_1$ and make a new function $h(n) = h_1(n)+5$. This heuristic is not admissible, but if you run A* on it, it will still find optimal solutions.
But, we also have to ask what you mean by "the optimality of A*", because optimality can have two senses here. My point in the previous paragraph is in the sense of returning optimal paths. An alternate interpretation is that no algorithm performs fewer expansions that A* with the same information. This is probably not what was meant, and the answer in that context is far more complicated. But, with an inconsistent (but admissible) heuristic, A* can perform exponentially more expansions than other known algorithms, and thus is not the optimal algorithm to use.

I am not sure what you mean here by "for any measure of best". Moreover, you say "I won't duplicate the proof here": can you please at least cite a resource that shows that any best-first algorithm finds the optimal solution (even if the heuristic is not admissible)?

See Lemma 1 in this paper: https://webdocs.cs.ualberta.ca/~nathanst/papers/chen2019conditions.pdf Note that I didn't claim that the optimal solution is found in this case, only that a solution will be found.


text:
What reinforcement learning algorithm should I use in continuous states?
I want to use reinforcement learning in an environment I made. The exact environment doesn't really matter, but it comes down to this: The amount of different states in the environment is infinite e.g. amount of ways you can put 4 cars at an intersection, but the amount of different actions is only 3 e.g. go forward, right or left. The state exists out of five numbers. My question is: what algorithm should I use or at least what kind of algorithm?

I would recommend looking at Deep Q-Learning.

Is DQN really good when there are infinite different states the environment can be

@SirPVP Yes, it is a function approximator method which is precisely for infinite state spaces.


text:
Why does L1 regularization yield sparse features?

In contrast to L2 regularization, L1 regularization usually yields sparse feature vectors and most feature weights are zero.

What's the reason for the above statement - could someone explain it mathematically, and/or provide some intuition (maybe geometric)?

This is a relatively old question, but, for reproducibility, could you please provide a link to the article/paper where you took this excerpt that you're quoting from?

Oops, at this point, I don't remember. I'll take care next time!

In L1 regularization, the penalty term you compute for every parameter is a function of the absolute value of a given weight (times some regularization factor).
Thus, irrespective of whether a weight is positive or negative (due to the absolute value) and irrespective of how large the weight is, there will be a penalty incurred as long as weight is unequal 0. So, the only way how a training procedure can considerably reduce the L1 regularization penalty is by driving all (unnecessary) weights towards 0, which results in a sparse representation.
Of course, the L2 regularization will also only be strictly 0 when all weights are 0. However, in L2, the contribution of a weight to the L2 penalty is proportional to the squared value of the weight. Therefore, a weight whose absolute value is smaller than 1, i.e. $abs(weight) < 1$, will be much less punished by L2 than it would be by L1, which means that L2 puts less emphasis on driving all weights towards exactly 0. This is because squaring a some value in (0,1) will result in a value of lower magnitude than taking the un-squared value itself: $x^2 < x\ for\ all\ x\ with\ abs(x) < 1$.
So, while both regularization terms end up being 0 only when weights are 0, the L1 term penalizes small weights with $abs(x) < 1$ much more strongly than L2 does, thereby driving the weight more strongly towards 0 than L2 does.


text:
What is the definition of the "cost" function in the SVM's objective function?
In a course that I am attending, the cost function of a support vector machine is given by
$$J(\theta)=\sum_{i=1}^{m} y^{(i)} \operatorname{cost}_{1}\left(\theta^{T} x^{(i)}\right)+\left(1-y^{(i)}\right) \operatorname{cost}_{0}\left(\theta^{T} x^{(i)}\right)+\frac{\lambda}{2} \sum_{j=1}^{n} \Theta_{j}^{2}$$
where $\operatorname{cost}_{1}$ and $\operatorname{cost}_{0}$ look like this (in Magenta):

What are the values of the functions $\operatorname{cost}_{1}$ and $\operatorname{cost}_{0}$?
For example, if using logistic regression the values of $\operatorname{cost}_{1}$ and $\operatorname{cost}_{0}$ would be $-\log* \operatorname{sigmoid}(-z)$ and $-\log*(1-\operatorname{sigmoid}(-z))$.

That is the hinge loss, a type of loss most notably used for SVM classification. The hinge loss is typically defined as:
$$
\ell(y)=\max (0,1-t \cdot y),
$$
which, in your use case, is something like this:
$$
\operatorname{cost}\left(h_{\theta}(x), y\right)=\left\{\begin{array}{ll}
\max \left(0,1-\theta^{T} x\right) & \text { if } y=1 \\
\max \left(0,1+\theta^{T} x\right) & \text { if } y=0
\end{array}\right.
$$
Check this article on it.


text:
Has reinforcement learning been used to prove mathematical theorems?
Coq exists, and there are other similar projects out there. Further, Reinforcement Learning has made splashes in the domain of playing games (a la Deepmind & OpenAI and other less well-known efforts).
It seems to me that these two domains deserve to be married such that machine learning agents try to solve mathematical theorems. Does anyone know of any efforts in this area?
I'm a relative novice in both of these domains, but I'm proficient enough at both to take a stab at building a basic theorem solver myself and trying to make a simple agent have a go at solving some basic number theory problems. When I went to look for prior art in the area I was very surprised to find none. I'm coming here as an attempt to broaden my search space.

This question seems to be very similar to https://ai.stackexchange.com/q/7416/2444 and https://ai.stackexchange.com/q/21382/2444. Can you clarify how your question is different from those?

well, I found those questions and they didn't really answer what I was looking for.  Reading the answers, they were answering much different parts of the question.  They are more interested in "is this possible? and if so, how?" and I'm more wondering about prior efforts to do this so I don't have to start from scratch. The answer given was pretty much perfect for me, so I'm glad it worked out.

This answer seems to answer your question. If it answers your question, you should at least upvote it.

i'm just going to leave this here: i hesitate to submit it as an answer since i am not in a position to evaluate the talk, but there is evidence that people are working on it!   https://www.youtube.com/watch?v=2m3zcGPKqws

Artificial Intelligence for Theorem Proving is an active research area as witnessed by the existence of the AITP conference and of many publications on the topic. Some papers are mentioned in this thread: https://coq.discourse.group/t/machine-learning-and-hammers-for-coq/303. I haven't read these papers myself, so I cannot point you to a paper using reinforcement learning specifically, but given the important activity in this domain, I would be very surprised if it hadn't been attempted.

Thanks a bunch! I found a few papers via the links you provided which is what I was looking for.

For anyone interested, this paper is essentially what I was looking for.  It has a benchmark, a.k.a. theorems that ought to be proved by the "theorem solver" with success rates for a few architectures they tried out. It also has an environment integration with an existing theorem solver "HOL Light" to build your own RI models against. The repository linked in their paper is here.

An updated paper in which they don't seed their model with human proofs is here.


text:
Implementing SARSA for a 2-stage Markov Decision Process
I am a bit confused as to how exactly I should be implementing SARSA (or Q-learning too) on what is a simple 2-stage Markov Decision Task. The structure of the task is as follows:

Basically, there are three states $\{S_1,S_2,S_3\}$ with $S_1$ is in the first stage for which the two possible actions are the two yellow airplanes. $S_2$ and $S_3$ are the possible states for the second stage and the feasible actions are the blue and red background pictures, respectively. There is only a reward at the end of the second stage choice. If I call the two first stage actions $\{a_{11},a_{12}\}$ and the four possible second stage actions $\{a_{21},a_{22},a_{23},a_{24}\}$, from left to right, then a sample trial/episode will look like:
$$S_1, a_{11}, S_2, a_{22},R \quad \text{ or }\quad S_1, a_{11}, S_3, a_{24}, R.$$
In the paper I am reading, where the figure is from, they used a complicated version of TD$(\lambda)$ in which they maintained two action-value functions $Q_1$ and $Q_2$ for each stages. On the other hand, I am trying to implement a simple SARSA update for each episode $t$:
$$Q_{t+1}(s,a)= Q_t(s,a) + \alpha\left(r + \gamma\cdot Q_t(s',a') - Q_t(s,a)\right).$$
In the first-stage, there is no reward so an actual realization will look like:
$$Q_{t+1}(S_1, a_{11}) = Q_t(S_1,a_{11})+\alpha\left( \gamma\cdot Q_t(S_3,a_{23}) - Q_t(S_1,a_{11})\right).$$
I guess my confusion is then how should it look like for the second stage of an episode? That is, if we continue the above realization of the task above, $S_1, a_{11}, S_3, a_{23}, R$, would should fill in the $?$:
$$Q_{t+1}(S_3,a_{23}) = Q_t(S_3,a_{23}) + \alpha\left(R +\gamma\cdot Q_t(\cdot,\cdot)-Q_t(s_3,a_{23}) \right)$$
One on hand, it seems to me that since this is the end of an episode, we assign $0$ to the $Q_t(\cdot,\cdot).$ On the other hand, the nature of this task is that it repeats the same episode over time for a total of $T$, a large number, times we need $Q_t(\cdot,\cdot) = Q_t(S_1,\cdot),$ with the additional action-selection in the first stage there.
I will greatly appreciate if someone can tell me what is the right way to go here.
The link to paper

You say "In the paper I am reading" - could you please link that resource, as it may explain why the writers are using what appears to be an over-complicated approach to solve a trivial-looking toy problem.

@NeilSlater I added the link to the paper. I should mention that the research is roughly about modeling human decision-making, especially that of those who have some impairment. As such, the focus is hardly about finding an optimal solver.
But my question is very simple - I want to start very simple by implementing a basic SARSA, which I did; however, the simulations I got look very different and wrong even, so I am guessing that my implementation is wrong.

Thanks for adding the link. I didn't read the paper yet, but would expect the researchers are implementing inverse reinforcement learning given the stated goal. That could be dificult to follow if you want to study classic RL used for optimal control.

In this game you can view end of an episode two ways:

There is an implied, terminal, fourth state $s_4$ representing the end of the game.

You could view the process as a continuous repeating one, where no matter what the choice is made in $s_2$ or $s_3$, the following state is $s_1$.

The first, terminating, view is a simpler and entirely natural view since nothing that the agent does in one episode can influence the next. It will result in a Q table that predicts future rewards within a single episode for the current agent (as opposed to discounted view over multiple episodes).
You are over-complicating things for yourself by ignoring that a zero reward is still a reward (of $0$). There is no need to remove $R$ from your initial update rule. In many environments there are rewards collected before the end of an episode.
In addition, to complete the standard episodic view, you can note that $Q(s_4, \cdot) = 0$ always by definition, hence so does $\text{max}_{a'}[Q(s_4, a'] = 0$. It is common here though to have a branch based on detecting a terminal state, and use a different update rule:
$$Q_{t+1}(S_3,a_{23}) = Q_t(S_3,a_{23}) + \alpha\left(R - Q_t(s_3,a_{23}) \right)$$
In brief, most implementations of TD algorithms do this:

Always assume a reward on each time step, which can be set to $0$

Special case for end of episode with a simplified update rule, to avoid needing to store, look up or calculate the $0$ value associated with terminal states

When implementing the environment, it is common to have a step function that always returns reward, next state and whether or not it is terminal e.g.
reward, next_state, done = env.step(action)

Details may vary around this. If you are working with an environment that does not have such a function (many will not have an inherent reward), then it is common to implement a similar function as a convenient wrapper to the environment so that the agent code does not have to include calculations of what the reward should be or whether the state is terminal.

Thank you - this makes things clear. However, I have one more question. The task is just people are playing this two stage MDP for a total of say $T = 200$ trials or episodes. In this view, humans are obviously learning things from episode to episode, albeit to a small extent; therefore, would it better to implement it in the second way you propose, as one continuing Markov Task with one episode and $T$ time steps?

@dezdichado: The learning problem is still solved by the strict episodic view, assuming you keep the Q table between episodes. I assumed this - were you thinking to reset it?. Repeating the episodes allows the learner to explore different approaches and figure out which is best - which is why it is being repeated, because the point is to study learning through trial and error. There are cases where you might want to think about aggregating reward over multiple episodes, but even then it is simpler and easier to analyse if you stick with the strictly episodic view for Q values and update rules.

Sorry to bother you again but I am now transitioning from matlab to python and in doing so, I am rewriting all my codes in a more scalable, object-oriented fashion. I was wondering if could point me to a code that writes the environment in customizable manner. I did do google searches and all the implementations I could find use the openai gym interface, which as a whole is a rather advanced for a beginner programmer like me.

@dezdichado The basic gym interface for environments is a reasonable design for a standardised framework in my opinion. I have not worked with any other similar libraries in any depth. Sorry I cannot help further.


text:
Why is 100% exploration bad during the learning stage in reinforcement learning?
Why can't we during the first 1000 episodes allow our agent to perform only exploration?
This will give a better chance of covering the entire space state. Then, after the number of episodes, we can then decide to exploit.

Why can’t we during the first 1000 episodes allow our agent perform only exploration

You can do this. It is fine to do so either to learn the value function of a simple random policy, or when performing off-policy updates. It is quite normal when learning an environment from scratch in a safe way - e.g. in simulation - to collect an initial set of data from behaving completely randomly. The amount of this random data varies, and usually the agent will not switch from fully random to fully deterministic based on calculated values as a single step, but will do so gradually.

this will give a better chance of covering the entire space state

That will depend on the nature of the problem. For really simple problems, it may explore the space sufficiently to learn from. However, for many problems it is just a starting point, and not sufficient to cover parts of the space that are of interest in optimal control.
When behaving completely randomly, the agent may take a very long time to complete an episode, and may never complete its first episode. So you could be waiting for a long time to collect data for the first 1000 such episodes. An example of this sort of environment would be a large maze - the agent will move back and forth in the maze, revisiting same parts again and again, where in theory it could already be learning not to repeat its mistakes.
In some environments, behaving completely randomly will result in early failure, and never experiencing postive rewards that are available in the environment. An example of this might be a robot learning to balance on a tightrope and get from one end to the other. It would fall off after a few random actions, gaining very little knowledge for 1000 episodes.
The state space coverage you are looking for ideally should include the optimal path through the space - at least at some point during learning (not necessarily the start). This does not have to appear in one single perfect episode, because the update rules for value functions in reinforcement learning (RL) will eventually allocate the correct values and find this optimal path in the data. However, the collected data does need to include the information about this optimal path amongst all the alternatives so that the methods in RL can evaluate and select it. In simple environments acting randomly may be enough to gain this data, but becomes highly unlikely when the environments are more complex.

then after the number of episodes, we can then decide to exploit

Again this might work for very simple environments, where you have collected enough information through acting randomly to construct a useful value function. However, if acting randomly does not find enough of the optimal path, then the best that exploitation can do is find some local optimum based on the data that was collected.
I suggest you experience this difference for yourself: Set up a toy example environment, and use it to compare different approaches for moving between pure exploration and pure exploitation. You will want to run many experiments (probably 100s for each combination, averaged) to smooth out the randomness, and you can plot the results to see how well each approach learns - e.g. how many time steps (count time steps, not episodes, if you are interested in sample efficiency) it takes for the agent to learn, and whether or not it actually finds the correct optimal behaviour. Bear in mind that the specific results will only apply in your selected environment - so you might also want to do this comparison on a small range of environments.

Ohh, using exploration wouldn’t be able to improve much of the optimal path, I get it, so the Q value estimates wouldn’t be that good since your agent wouldn’t land on those states as often as they do during exploitation, am I right

@Chukwudi: Yes. But as usual this depends heavily on the nature of the environment. I have successfully trained an RL agent to play Tic Tac Toe 100% optimally, learning purely from random moves (for 50,000 episodes), then exploiting the value table that it built. However, the same approach does not work well at all for Connect 4. The way you word your questions, it seems you are looking for hard rules why things should work or not, but RL covers such a large range of problems, that this is not really possible,

Oh I get it now, it’s not a question that can be given a concrete answer, it all depends on the type of environment, what works for one, might not work on the other

@Chukwudi: Yes. There are lots of questions like that in RL. Often when someone here has said "that won't work" to one of your questions, and gives an example why, they mean "that won't work in general, and here's a counter-example".

So the safest way is to gradually decay our exploration rate

Neil, the same user recently asked this question. Isn't this just a duplicate?

@nbro: Yes it is. Sorry I missed that. The answers there are OK, but given accpeted answer is here, perhaps the other could be closed as duplicate of this?

Close the other one, these answers are more suited to my question


text:
What is meant by the number of channels of a network?
Currently, I am reading Rethinking Model Scaling for Convolutional Neural Networks. The authors are talking about a different way of scaling convolutional neural networks by scaling all dimensions simultaneously and relative to each dimension. I understand the scaling methods regarding the depth of a network (# layers) and the resolution (size of the input image).
What I was stumbling is the concept of the network's width (# channels). What is meant by the width or the number of channels of a network? I don't think it is the number of color channels, or is this the case? The number of color channels was the only link I found regarding the terms "ConvNets" and "number of channels".

It's not clear to me the relationship between "network's width" and "number of channels". Do the authors use the term "width" to refer to the "number of channels" in the paper? That would be very strange.

It is exactly that - the number of color channels or any other analogue to color that you use.

Ok, I did not know this.. I thought, the max color space of an image with space = 3 would be 3. But instead, I could also synthetically increase the color space to 32 or some other number, correct?

Yes, that's right. And you also can use CNNs not only for regular images, you can analyze any data that is intrinsically 2-dimentional.


text:
Why don't we use trigonometric functions for the output neurons?
Why don't we use a trigonometric function, such as $\tan(x)$, where $x$ is an element of the interval $[0,pi/2)$, instead of the sigmoid function for the output neurons (in the case of classification)?

Are you only interested in classification or also regression?

In classification. I'm curious as to why we fit the data using a sigmoid function.

Although it's true that if you use certain trigonometric functions, such as the tangent, you could have numerical problems (as suggested in this answer), that's not the only reason for not using trigonometric functions.
Trigonometric functions are periodic. In general, we may not want to convert a non-periodic function to a periodic one. To be more concrete, let's suppose we use the sine function as the activation function of the output neurons of a neural network. Assuming only one input, if the input to any of those output neurons is $360k$, for any integer $k$, the result will always be $0$, but that may not be desirable.

The main reason why the sigmoid function is used is because it 'does not blow up' since it is between 0 and 1 always. As for the relu it is used because it is computationally cheap and even resolves the problem of vanishing gradient(and hence used more often than sigmoid).
So a function like tan(x) will blow up for certain values of x. This can cause a problem of exploding gradients. So, I believe for this reason tan(x) cannot be a good non-linearity to be used.
As for any other function, it is more because of the results that we have gotten over the years and sigmoid and relu have been promising.


text:
Does "transition model" alone in an MDP imply it's non-deterministic?
I am looking at a lecture on POMDP, and the context is that, when the quadcopter can't see the landmarks, it has to use reckoning. And then he mentions the transition model is not deterministic, hence the uncertainty grows.
Can transition models in MDP be deterministic?

Yes, in which case, it will be more like a search problem, if it is not POMDP and have finite number of states. Or you can use the same framework (used for POMDP) with constrained (deterministic) transition matrix modeling for model-based systems.
If you think about it after you train any model/agent with an MDP modeling, during test time the optimal strategy is generally deterministic, i.e., given a feature/state you will take a particular action even if it has more than one non-zero element in each row of the transition matrix.

Alright, when you say deterministic strategy you mean we select argmax or the maximum result? Can you please elaborate constrained (deterministic) transition matrix

Yes, I was referring to the best strategy obtained with argmax.

When you have a deterministic transition, the actions are irrelevant, since choosing an action is equivalent to reaching a state, so you can in simple cases use dynamic programing/Beam search to solve the problem. In complex cases, the reward can be infinite and you can use value iteration to solve the problem. I found some paper on the topic which might help you related work "Max-Plus Matching Pursuit for Deterministic Markov
Decision Processes" https://arxiv.org/pdf/1906.08524.pdf

allright makes sense! I accepted your answer as now it is clear. I have a small followup question. How can a transition be deterministic if the environment is stochastic? So say if I move left there is 30% chance that i will transition to front instead of left. So when you say actions are irrelevant, you mean to say we dont care about the 30% chance of transitioning to front if we intend to move left?

I think there is a misunderstanding. Transition matrix being deterministic means when you take an action you are certain that you will end up in only one state, which means the environment is deterministic. In this case (deterministic environment/transition matrix) actions are irrelevant. "So say if I move left there is 30% chance that i will transition to front instead of left." - this means the environment/transition matrix is stochastic.

+1 This clarifies my confusion. I was confused by the underlying assumption where environment was stochastic and transition matrix was deterministic.

Yes , a transition model shows that our environment is stochastic in nature, and with that model we know the probability of entering a state when an action is taken.


text:
Why do we update the weights of the target network in deep Q learning?
I know we keep the target network constant during training to improve stability, but why exactly are we updating the weights of our target network? In particular, if we've already reached convergence, why exactly are we updating the weights of our target network?

If you are certain that you reached convergence then there is no point in continuing to train your agent, because of that there is also no point in discussing why is target network being updated after convergence is reached. You should simply stop training if you converged. During training we obviously need to keep updating target network to improve correctness of Q-value estimates.


text:
What happens when you select actions using softmax instead of epsilon greedy in DQN?
I understand the two major branches of RL are Q-Learning and Policy Gradient methods.
From my understanding (correct me if I'm wrong), policy gradient methods have an inherent exploration built-in as it selects actions using a probability distribution.
On the other hand, DQN explores using the $\epsilon$-greedy policy. Either selecting the best action or a random action.
What if we use a softmax function to select the next action in DQN? Does that provide better exploration and policy convergence?

DQN on the other hand, explores using epsilon greedy exploration. Either selecting the best action or a random action.

This is a very common choice, because it is simple to implement and quite robust. However, it is not a requirement of DQN. You can use other action choice mechanisms, provided all choices are covered with a non-zero probability of being selected.

What if we use a softmax function to select the next action in DQN? Does that provide better exploration and policy convergence?

It might in some circumstances. A key benefit is that it will tend to focus on action choices that are close to its current best guess at optimal. One problem is that if there is a large enough error in Q value estimates, it can get stuck as the exploration could heavily favour a current best value estimate. For instance, if one estimate is accurate and relatively high, but another estimate is much lower but in reality would be a good action choice, then the softmax probabilities to resample the bad estimate will be very low and it could take a very long time to fix.
A more major problem is that the Q values are not independent logits that define preferences (whilst they would be in a Policy Gradient approach). The Q values have an inherent meaning and scale based on summed rewards. Which means that differences between optimal and non-optimal Q value estimates could be at any scale, maybe just 0.1 difference in value, or maybe 100 or more. This makes plain softmax a poor choice - it might suggest a near random exploration policy in one problem, and a near determinitsic policy in another, irrespective of what exploration might be useful at the current stage of learning.
A fix for this is to use Gibbs/Boltzmann action selection, which modifies softmax by adding a scaling factor - often called temperature and noted as $T$ - to adjust the relative scale between action choices:
$$\pi(a|s) = \frac{e^{q(s,a)/T}}{\sum_{x \in \mathcal{A}} e^{q(s,x)/T}}$$
This can work nicely to focus later exploration towards refining differences between actions that are likely to be good whilst only rarely making obvious mistakes. However it comes at a cost - you have to decide starting $T$, the rate to decay $T$ and an end value of $T$. A rough idea of min/max action value that the agent is likely to estimate can help.

So, using softmax could be considered a substitute for other exploration trick?

@HermesMorales: Yes it is a way to construct a flexible exploring policy


text:
What is the bias-variance trade-off in reinforcement learning?
I am watching DeepMind's video lecture series on reinforcement learning, and when I was watching the video of model-free RL, the instructor said the Monte Carlo methods have less bias than temporal-difference methods. I understood the reasoning behind that, but I wanted to know what one means when they refer to bias-variance tradeoff in RL.
Is bias-variance trade-off used in the same way as in machine learning or deep learning?
(I am just a beginner and have just started learning RL, so I apologize if it is a silly question.)

The bias-variance trade-off that you're referring to has to do with the return estimator. Any RL algorithm you choose needs some estimate of the cumulative return, which is a random variable with many sources of randomness, such as stochastic transitions or rewards.
Monte Carlo RL algorithms estimate returns by running full trajectories and literally averaging the return achieved for each state. This imposes very few assumptions on the system (in fact, you don't even need the Markovian property for these methods), so bias is low. However, variance is high since each estimate depends on the literal trajectories that you observe. As such, you'll need many, many trajectories to get a good estimate of the value function.
On the other hand, with TD methods, you estimate returns as $R_t + \gamma V(S_{t+1})$, where $V$ is your estimate of the value function. Using $V$ this imposes some bias (for instance, the initialization of the value function at the beginning of training affects your next value function estimates), with the benefit of reducing variance. In TD learning, you don't need full environment rollouts to make a return estimate, you just need one transition. This also lets you make much better use of what you've learned about the value function, because you're learning how to infer value "piecewise" rather than just via literal trajectories that you happened to witness.

It may also be a good idea to mention TD($\lambda$), so that people don't think that the distinction between the 2 approaches is always sharp.


text:
How to handle the final state in experience replay?
I'm using the DQN algorithm to train my agent to play a turn-based game. The memory replay buffer stores tuples of experiences $(s, a, r, s')$, where $s$ and $s'$ are consecutive states. At the last turn, the game ends, and the non-zero reward is given to the agent. There are no more observations to be made and there is no next state $s'$ to store in the experience tuple. How should the final states be handled?

This question seems to be a duplicate of this.

You do not store a terminal state as $s$ in the replay table because by definition its value is always $0$, and there is no action, reward or next state. There is literally nothing to learn.
However, you may find it useful to store information that $s'$ is actually a terminal state, in case this is not obvious. That is typically achieved by storing an additional done boolean component. This is useful, because it allows you to branch when calculating the TD target g:
s, a, r, next_s, done = replay_memory_sample()
if done:
  g = r
else:
  g = r + gamma * max( q(s') )


text:
Why do we explore after we have an accurate estimate of the value function?
Suppose we have a small space state and that, after about 2000 episodes, we've accurately explored the environment and known the accurate $Q$ values. In that case, why do we still leave a small probability for exploration?
My guess is in the case of a dynamic environment where a bigger reward might pop up in another state. Is my assumption correct?

Suppose we have a small space state and that, after about 2000 episodes, we've accurately explored the environment and known the accurate $Q$ values. In that case, why do we still leave a small probability for exploration?

It will depend on the goal of the work:

If the learning algorithm is off-policy (e.g. Q learning), it is normal to continue to explore at a moderate-to-low rate because it can accurately estimate an optimal deterministic target policy from a close-to-optimal stochastic behaviour policy.

Perhaps it is engineered with a low tolerance and will keep going even when you don't need it to.

Perhaps the code is for education and run so long that convergence is easily visible. Or for comparison with other methods which really do take that long to converge, and you would like data on the same axis.

For comparison with other methods for sample efficiency whilst learning and measuring regret (i.e. how much the exploration is costing you).

When environment is dynamic and could change, then continuous exploration is potentially useful to discover the changes, as you suggest in the question.

If you do really have an ideal agent, then of course you could just stop and say "job done". In practice for more interesting problems, you won't usually get small state spaces and perfect solutions inside 2000 episodes (or ever) - as a result if you are reading tutorials in reinforcement learning, they may just skip this point.

Ok so due to the randomness of the environment, it’s ideal to always keep exploring in case of new changes to the environment?

And since small space states are rare, it’s also possible that our space state is close to infinite and therefore even 2000 episodes isn’t enough to have accurate Q values ?

@Chukwudi: It all depends. However, those are both valid reasons to continue exploring if they are true for your problem.

Is there anyway I could have a personal chat with you ?

@Chukwudi: Sure - it's a public chat mind - here - https://chat.stackexchange.com/rooms/info/109789/why-do-we-explore-after?tab=general - I am happy to talk about refinements to the question and answer here, but I don't want to take role of persoanl tutor or debug any personal projects etc.

When you are training a system using stochastic gradient descent, your system will converge towards some local minimum. If the local minimum was a good one, we would be fine with it. However, we cannot know how good a found solution is in comparison to other solutions of which we do not know their quality because they have been insufficiently explored. So, continuing to explore is a good way to escape comparatively bad local minima even if training has progressed already for quite a bit.
Besides that, maybe even more importantly towards the end of training, one also wants the system to perform well, i.e. robustly, in the presence of noise and not just under ideal circumstances. So, introducing some randomness, i.e. noise, into the network's policy can also lead to more robust policies being learned since the agent gets trained on how to best recover failure/unforeseen transitions into unexpected states.

So due to the randomness of the environment( for example a new reward might pop up) it’s ideal to always keep exploring

Consider the case where an agent has to move across some environment and occasionally slips out or gets displaces by some unforeseen event, e.g. by being displaced by a user (might happen to your lawn mowing robot if you realize that it notoriously misses to visit one particular spot in your garden). Then, the agent will have to no idea how to behave in that situation/state, except for random guessing, if the weights of the network containing the agent's policy have never been trained on coping with such an unforeseen state suddenly being encountered for the first time after training is done).

Ok so basically we train our agent , it goes to the real world , and at a particular state it was trained to always go up , now if there’s an external interference, where always going up makes it land in a pit, it wouldn’t know what to do and will be confused right, so it’s best we give some randomness

Yes, because the randomness shall at least somewhat prepare the agent towards how to cope with being in that pit. Maybe the agent hasn't encountered that specific specific situation yet when getting trapped during run time for the first time, but at least it could have encountered comparable situations during training that could enable it to have at least somewhat accurate estimates of Q-values for the novel situation. And that is only achieved if there is at least some exploration constantly throughout training.

Can we assume the pit it landed in is another state, if it’s another new state it means it has no Idea of what to do in that state since all Q values are 0, so basically giving a chance of exploring is a good thing

Yes, as long as the degree of exploration doesn't interfere with the eventual convergence to a reasonably good policy, exploration is a good thing.
And yes, a pit would be a new, distinct environmental state. But please note that a pit could be similar to other, similar training situations/states encountered beforehand during training. So, even if a particular state has not explicitly been visited during training, the deep RL agent can still learn how to cope with such a novel state given the generalization ability of the policy-network it employs.

B I kind of get it , if we’re using a neural network, our function approximator would Be able to provide close to accurate Q values of the new state it encountered, regardless of whether it had visited the state during its training


text:
Intuitively, why can the training of a neural network be formulated as a probability estimation problem?
Neural network training problems are oftentimes formulated as probability estimation problems (such as autoregressive models).
How does one intuitively understand this idea?

Consider the case of binary classification, i.e. you want to classify each input $x$ into one of two classes: $y_1$ or $y_2$. For example, in the context of object classification, $y_1$ could be "cat" and $y_2$ could be "dog", and $x$ is an image that contains one main object.
In certain cases, $x$ cannot be easily classified. For example, in object classification, if $x$ is a blurred image where there's some uncertainty about the object in the image, what should the output of the neural network be? Should it be $y_1$, $y_2$, or maybe it should be an uncertainty value (i.e. a probability) that lies between $y_1$ and $y_2$? The last option is probably the most reasonable, but also the most general one (in the sense that it can also be used in the case there's little or no uncertainty about what the object is).
That's the reason why we can model or formulate this (or other) supervised learning problem(s) as the estimation of a probability value (or probability distribution).
To be more concrete, you can formulate this binary classification problem as the estimation of the following probability
\begin{align}
P(y_1 \mid x, \theta_i) \in [0, 1] \label{1}\tag{1}
\end{align}
where $y_1$ is the first class (or label), $(x, y) \in \mathcal{D}$ is a labeled training example, where $y$ is the ground-truth label for the input $x$, $\theta_i$ are the parameters of the neural network at iteration $i$, so, intuitively, $P(y_1 \mid x, \theta_i) $ is a probability that represents how likely the neural network thinks that $x$ belongs to the class $y_1$ given the current estimate of the parameters. The probability that $x$ belongs to the other class is just $1 - P(y_1 \mid x, \theta_i) = P(y_2 \mid x, \theta_i)$.  In this specific case, I have added a subscript to $\theta$ to indicate that this probability depends on the $i$th estimate of the parameters of the neural network.
Once you have $P(y_1 \mid x, \theta_i)$, if you want to perform classification, you will actually need to choose a threshold value $t$, such that, if $P(y_1 \mid x, \theta_i) > t$, then $x$ is classified as $y_1$, else it is classified as $y_2$. This threshold value $t$ can be $0.5$, but it can also not be.
Note that, in the case above, $P(y_1 \mid x, \theta_i)$ is a number and not a probability distribution. However, in certain cases, you can also formulate your supervised learning problem so that the output is a probability distribution (rather just a probability). There are also other problems where you don't estimate a conditional probability but maybe a joint probability, but the case above is probably the simplest one that should give you the intuition behind the idea of formulating machine learning problems as the estimation of probabilities or probability distributions.