Improved regret bound for DRL

by Vanessa Kosoy 1 min read2nd Mar 2018No comments

0


% 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

#Theorem 1

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

Assume that

i. For each , .

ii.

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):

#Proposition 1

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

0