0
$\begingroup$

In online reinforcement learning theory, how to judge the complexity order of regret, if there are two or more terms in there?

For example, the state space is $X$, the action space is $A$, the episode number is $K$, and the horizon number is $H$. If we have an algorithm with regret $R_K=2X^2A H \ln K \ln H + 3XAH^2\ln K$.

How can I decide the order of this algorithm? Should we look at which term is dominant with respect to the episode number $K$ or total steps $T=HK$? Then it might be $O(XAH^2\ln K)$

Or also consider the relationship with the state and action space? Then it might be $O(X^2AH^2\ln K)$, here I choose the highest order of each variable in both terms.

Improve this question
$\endgroup$
2
  • $\begingroup$ Too many parameters :) $\endgroup$
    – mathworker21
    Jun 9 at 9:29
  • $\begingroup$ Yeah. To briefly understand the meanings of parameters, you can consider that there are $K$ different policies $\pi_k, k =1,\cdots, K$ with episodes going on. For each policy, the agent will make decisions according to the policy for $H$ steps, and get his rewards and feedback on these steps. And then update the policy to the next episode. Then the total interaction steps will be $T=HK$. Regret is the difference between the cumulative reward of the $K$ episodes according to the online updated policies and that according to an unknown optimal static policy. $\endgroup$
    – white
    Jun 9 at 11:01

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.