I came across the formula for Upper Confidence Bound Action Selection (while studying multi-armed bandit problem), which looks like:
$$ A_t \dot{=} \operatorname{argmax}_a \left[ Q_t(a) + c \sqrt{ \frac{\ln t}{N_t(a)} } \right] $$
Although, I understand what the second term in the summation actually means but I am not able to figure out how and from where the exact expression came from, what is the log doing there? What effect does $c$ have? And, why a square root?
Here is an intuitive description/explanation.
$c$ is there for a trade-off between exploration and exploitation. If $c=0$ then you only consider $Q_t(a)$ (no exploration). If $c \rightarrow \infty$ then you only consider exploration term.
$\frac{\ln t}{N_t(a)}$ is there to balance out exploration term. If you consider a simple case where you only have one action (then it wouldn't make sense to explore you could always pick that action but let's pretend there is) then as $t \rightarrow \infty$, because $\ln t$ has sublinear growth,
\begin{equation}
\frac{\ln t}{N_t} \rightarrow 0
\end{equation}
So, after you picked an action infinitely many times, the exploration term will completely diminish, i.e. you already know a lot about what that action does. If you picked a numerator that doesn't have sublinear growth, then as $t \rightarrow \infty$ exploration term would not diminish, so you would always have a chance to explore and exploration term can "overpower" action value term if $Q_t$ is very small, even after you picked an action infinitely many times, which is not desired.
A similar thing is with multiple actions, $\ln t$ will make sure the exploration term $\rightarrow 0$ if you picked it many times, but it's still better than constant term $K/N_t(a)$, where $K$ is some constant, because it can diminish too fast.
With $\ln t$ you will also not stop exploring completely if you haven't picked some action in a long time, because $\ln t$ will keep growing and $N_t(a)$ will remain the same, so their fraction will increase with time, which is useful in non-stationary environments.
The square root is also there probably to balance out the magnitude of exploration term.
You can also see this answer. It has couple of links to some papers for a more mathematical description.
