# Some questions on kernels and Reinforcement Learning

I've a test in a few days and I've a few issues with some of the subjects.

Let's start with kernels, basically I understood that a kernel needs to be positive semi-definite and symmetric in order to be valid. Is that enough? For example the following kernel, $\mathrm{kernel}(x,y) = 2 k(x,y)$ for some $k$ which is a valid kernel. Is that valid? My question is how can I distinguish between a valid kernel and an invalid kernel if I'm given a kernel in the test?

Reinforcement learning - Value iteration, upper bound confidence and Q-learning. I'm trying to figure out the major differences between them, Value Iteration is when we are familiar with the world, with the probabilities and such. And Q-learning is basically learning the world first. Where does upper bound confidence enter?

Thanks.

• Welcome to CS.SE! Can you ask these as two separate questions (e.g., edit this question to remove the second one, and post it separately via the 'Ask Question' button)? – D.W. Jul 23 '17 at 16:31
• What you require of a kernel depends on what you use it for. Sometimes we also want the kernel to be invertible, or even to have good condition number. – Yuval Filmus Jul 23 '17 at 17:40

Is that valid? My question is how can I distinguish between a valid kernel and a nonvalid kernel if I'm given a kernel in the test?

Yes, it will be a valid kernel for all practical purposes, because kernel functions measure the similarity of some points relative to other ones (that's why they are also called similarity functions). Making your kernel function twice as big doesn't change that.

The next quote is from Wikipedia:

Although no single definition of a similarity measure exists, usually such measures are in some sense the inverse of distance metrics: they take on large values for similar objects and either zero or a negative value for very dissimilar objects. E.g., in the context of cluster analysis, Frey and Dueck suggest defining a similarity measure $s(x,y)=-\|x-y\|_{2}^{2}$ where $\|x-y\|_{2}^{2}$ is the squared Euclidean distance.

As you can see, a kernel function can be negative, if that's convenient in a particular problem. I don't know any example of an asymmetric kernel function. See this question for more examples.

The answer to your question boils down to this: can you apply a particular kernel function to a particular method? So it depends on a problem to large extent.

Where does upper bound confidence enter?

In general, Upper Confidence Bound (UCB) is a Bayesian Optimization method, that aims to deal with exploration-exploitation trade off in the multi-armed bandit problem. In this problem, there is an unknown function, which we can evaluate in any point, but each evaluation costs (direct penalty or opportunity cost), and the goal is to find its maximum using as few trials as possible. Basically, the trade off is this: you know the function in a finite set of points (of which some are good and some are bad), so you can try area around the current local maximum, hoping to improve it (exploitation), or you can try a completely new area of space, that can potentially be much better or much worse (exploration), or somewhere in between.

Just as a side note, Bayesian Optimization methods, UCB in particular, build a model of the target function using a Gaussian Process (GP) and at each step choose the most "promising" point based on their GP model.

In Reinforcement Learning, the same exploration-exploitation dilemma arises as well. When an agent chooses an action to make, it has a choice between low uncertainty actions with a known value (exploitation) and high uncertainty actions (exploration). Without proper exploration, an agent would always do the same actions and never actually learn.

In this setting, UCB is counting how many times each action $a$ has been selected, $N_t(a)$, and maximizes the following expression:

$a_t = \underset{a∈A}{\operatorname{argmax}} Q(a) + \sqrt \frac{2 log t}{N_t(a)}$

where $Q(a)$ is an action-value function. If you compare this formula to the one used in Bayesian Optimization, you'll notice it's actually the same idea.