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.

  • $\begingroup$ Too many parameters :) $\endgroup$ Commented Jun 9, 2023 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
    Commented Jun 9, 2023 at 11:01


Your Answer

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