% operators that are separated from the operand by a space
% autosize deliminaters
% operators that require brackets
% operators that require parentheses
% Paper specific
There is a simple way to somewhat improve the regret bound for DRL we derived before. Specifically, we have the following
There is some s.t. the following holds.
Consider an interface, , for some . For each , let be an -sane policy for . For each , let be the corresponding MDP. Denote
i. For each , .
Then, there is an -policy s.t.
This gives gives us better dependence on but worse dependence on compared to what we had before. However, we can also get the best of both bounds with a single algorithm, since the only difference between the algorithms is in the choice of the parameters and (which can be chosen to give the better of the two bounds for the given parameters).
To show Theorem 1, we use the following proposition which appears in Russo and Van Roy as Proposition 3 (see page 16):
Consider a probability space , , a finite set and random variables , and . Assume that and . Then
Theorem 1 is now proved exactly as before, with Proposition 1 replacing what was previously called Proposition B.3 and setting and to