The complexity order of regret (especially in online reinforcement learning)?

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.

• Too many parameters :) Jun 9 at 9:29
• 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. Jun 9 at 11:01