10 Regret Optimal

Finally, substituting the upper bounds from Eqns.(33)and(35)in the regret upper bound in Eqn. Note that inequality (a) holds with equality for binary vectorsy {0,1}mN. Let y be a solution of the relaxed LP(9), and OPT be the optimal value of the problem(8). As discussed before, the corresponding physical cache configurationyt may be obtained using the mapping ψ(). LetSk be the time of thekth renewal,k 1 [Ross, 1996].