In this talk, we will revisit the classical regret-minimization problem in the multi-armed bandit setting.

The Strahler number of a rooted tree is the largest height of a perfect binary tree that is its minor.

A directed graph is said to be k-vertex-connected if after deleting any k-1 vertices, therer is a directed path from every vertex to every other vertex along the directed edges.

Given n-variate polynomials f,g,h such that f=g/h, where both g and h are computable by arithmetic circuits of size s, we show that f can be computed by a circuit of size poly(s, deg(h)).

The \emph{orbit} of an n-variate polynomial f(\var x) over a field \F, denoted by \orbit{f}, is the set of polynomials obtained by applying invertible affine transformations on the variables of f(\var x), and the orbit of a polynomial class is the