# What is the meaning of “exploration” in reinforcement and supervised learning?

While exploration is an integral part of reinforcement learning (RL), it does not pertain to supervised learning (SL) since the latter is already provided with the data set from the start.

That said, can't hyperparameter optimization (HO) in SL be considered as exploration? The more I think about this the more I'm confused as to what exploration really means. If it means exploring the environment in RL and exploring the model configurations via HO in SL, isn't its end goal "mathematically" identical in both cases?

In reinforcement learning, exploration has a specific meaning, which is in contrast with the meaning of exploitation, hence the so-called exploration-exploitation dilemma (or trade-off). You explore when you decide to visit states that you have not yet visited or to take actions you have not yet taken. On the other hand, you exploit when you decide to take actions that you have already taken and you know how much reward you can get. It's like in life: maybe you like cereals $$A$$, but you never tried cereals $$B$$, which could be tastier. What are you going to do: continue to eat cereals $$A$$ (exploitation) or maybe try once $$B$$ (exploration)? Maybe cereals $$B$$ are as tasty as $$A$$, but, in the long run, $$B$$ are healthier than $$A$$.

More concretely, recall that, in RL, the goal is to collect as much reward as you can. Let's suppose that you are in state $$s$$ and, in the past, when you were in that state $$s$$, you had already taken the action $$a_1$$, but not the other actions $$a_2, a_3$$ and $$a_4$$. The last time you took action $$a_1$$, you received a reward of $$1$$, which is a good thing, but what if you take action $$a_2, a_3$$ or $$a_4$$? Maybe you will get a higher reward, for example, $$10$$, which is better. So, you need to decide whether to choose again action $$a_1$$ (i.e. whether to exploit your current knowledge) or try another action that may lead to a higher (or smaller) reward (i.e. you explore the environment). The problem with exploration is that you don't know what's going to happen, i.e. you are risking if you already get a nice amount of reward if you take an action already taken, but sometimes exploration is the best thing to do, given that maybe the actions you have taken so far have not led to any good reward.

In hyper-parameter optimization, you do not need to collect any reward, unless you formulate your problem as a reinforcement learning problem (which is possible). The goal is to find the best set of hyper-parameters (e.g. the number of layers and neurons in each layer of the neural network) that performs well, typically, on the validation dataset. Once you have found a set of hyper-parameters, you usually do not talk about exploiting it, in the sense that you will not continually receive any type of reward if you use that set of hyper-parameters, unless you conceptually decide that this is the case, i.e., whenever you use that set of hyper-parameters you are exploiting that model to get good performance on the test sets that you have. You could also say that when you are searching for new sets of hyper-parameters you are exploring the search space, but, again, the distinction between exploitation and exploitation, in this case, is typically not made, but you can well talk about it.

It makes sense to talk about the exploitation-exploration trade-off when there is stochasticity involved, but in the case of the hyper-parameter optimization there may not be such a stochasticity, but it's usually a deterministic search, which you can, if you like, call exploration.

• Your last paragraph lies at the crux of my problem, it seems. Why would exploration in RL be any less deterministic than HO for SL? And vice-versa: After all, there is such a thing as stochastic gradient descent which also could be used in the context of HO. From your answer it seems that the difference in the is just in the semantics, but is there a more fundamental one? – Tfovid Sep 21 '20 at 11:01
• @Tfovid There usually no stochasticity in hyper-parameter optimization. It's just like this: try this set $A$, $B$, and $C$ of hyper-parameters, then choose the best one among them to test on the test dataset, and that's it (end of the story). Stochastic gradient descent is called stochastic for another reason: it's because you are using "noisy" approximations of the "true gradient". In a way, there's stochasticity in SGD, but it's conceptually different than in RL. – nbro Sep 21 '20 at 11:04
• In RL, you need to think of actions, rewards and environments, and think there's an agent that goes around in the environment taking actions and receiving rewards and the agent needs to decide which actions to take. The exploration-exploitation dilemma is one of the most important concepts of RL (if not the most important) because all RL algorithms need to face it. You really need to understand that exploration and exploitation have specific meanings in RL (which I describe in my answer above), but may not have specific meanings in other machine learning techniques. – nbro Sep 21 '20 at 11:08
• In RL, the environment is stochastic, i.e. in the sense that it's governed by probabilities. Maybe that will answer your question of why RL is "more stochastic". For example, if you take action $a$ in the state $s$, you may not always end up in the same next state or receive always the same reward. Have a look at the Markov decision process, which is the mathematical framework that underlies all RL algorithms. You will see that the MDP is composed of probabilities. – nbro Sep 21 '20 at 11:19
• If you want to show a mathematical difference between "exploration" in HO and RL, may be worth explaining the concept of regret. Although there is still an analogy (how much time/effort spent searching in HO), the definition in RL does not carry over to HO. – Neil Slater Sep 21 '20 at 11:55

In fact if the reward that you get are not stochastic in RL then you simply take a step into your parameter space that guaranteed you the best reward so far (after the evaluation of all other states). So for example if action up is the best one so far, nothing motivates you to try an other one.

When you are doing naïve HO it could be seen as an exploration of the space. The environment is not stochastic but the reward (loss decrease) that you will get are not known by the agent beforehand. That's enough to make the exploration step mandatory. So let's say the combination (up, up, down) has got you the best loss so far, you need to actually try other combinations to know if they are the best above all others. In that sense you are exploring too.

So when are you not exploring ? If the next step in your HO is given by an optimization step, let's say by a function $$f$$, then you are not exploring anymore. You are progressing toward the objective given by $$f$$.

Thus, you have to make sure that $$f$$ correctly gives you the best combination of parameters - mathematically $$f$$ is converging to a global optimum.

So grid search could be viewed as exploration, Bayesian optimization HO not that much.

• This "if action up is the best one so far, nothing motivates you to try an other one." is wrong. If you haven't tried all actions, how can you know that action "up" is the best among all other actions even if it's the best so far? – nbro Sep 22 '20 at 11:48
• When I wrote "so far" I meant when you have tried actually performed an estimation of the value of all actions. That's why I state that in that case you will always repeat that ''up'' action and be guaranteed that you are executing the best action so far because the environement is not stochastic. – MickAel Sep 22 '20 at 13:06
• Your answer can potentially be useful, but there are some parts that could be written more clearly. For example, "So when you are not ?", when you are not what? Maybe you should also explain why in BO you don't just explore. – nbro Sep 22 '20 at 13:28