Hi
Could you please explain how to obtain the value of m that maximises the bound of E[R]? And then how do we obtain the final bound for E[R]?
Thank you
Hello Marina,
Due to the imposed Lipschitzness of the reward we have that the reward around each grid point
changes at most linearly in 
. Moreover, since the grid points are spaced at a distance of 
apart, we can approximate the regret within each interval around a given grid point by the regret at grid point itself, with being off by at most 
.
Due to the imposed Lipschitzness of the reward we have that the reward around each grid point
changes at most linearly in . Moreover, since the grid points are spaced at a distance of apart, we can approximate the regret within each interval around a given grid point by the regret at grid point itself, with being off by at most .The only thing that remains is then to add approximation error to the bound obtained in i), plug in 
and optimize for 
(set derivative wrt. equal to 0).
Cheers,
Thomas
and optimize for (set derivative wrt. equal to 0).Cheers,
Thomas
Nevermind, 
is concave so setting the first derivative = 0 doesnt work. I will have another look later!
is concave so setting the first derivative = 0 doesnt work. I will have another look later!Hi Marina,
My first guess was actually correct. Applying the first-order optimality condition is permitted here because, asymptotically (for
), the term (which is convex!) dominates. Hence the objective function is (informally speaking) "asymptotically convex" and setting the first derivative to zero is sufficient and necessary for obtaining the (asymptotically) optimal choice of .
Best,
Thomas
My first guess was actually correct. Applying the first-order optimality condition is permitted here because, asymptotically (for
), the term (which is convex!) dominates. Hence the objective function is (informally speaking) "asymptotically convex" and setting the first derivative to zero is sufficient and necessary for obtaining the (asymptotically) optimal choice of .Best,
Thomas
Hi
I am trying again to do this computation but I am not able to compute the derivative. Can you help me out? Thank you
I am trying again to do this computation but I am not able to compute the derivative. Can you help me out? Thank you
Dear Marina,
Ignoring the big-O notation for a moment, the first derivative is equal to
. Setting this to zero and solving for , you obtain the optimal choice for (as I explained above, the first order optimality condition holds even though the function is strictly speaking not convex).
Best,
Thomas
Ignoring the big-O notation for a moment, the first derivative is equal to
. Setting this to zero and solving for , you obtain the optimal choice for (as I explained above, the first order optimality condition holds even though the function is strictly speaking not convex).Best,
Thomas
