<p>In online reinforcement learning theory, how to judge the complexity order of regret, if there are two or more terms in there?</p>
<p>For example, the state space is <span class="math-container">$X$</span>, the action space is <span class="math-container">$A$</span>, the episode number is <span class="math-container">$K$</span>, and the horizon number is <span class="math-container">$H$</span>. If we have an algorithm with regret <span class="math-container">$R_K=2X^2A H \ln K \ln H + 3XAH^2\ln K$</span>.</p>
<p>How can I decide the order of this algorithm? Should we look at which term is dominant with respect to the episode number <span class="math-container">$K$</span> or total steps <span class="math-container">$T=HK$</span>? Then it might be <span class="math-container">$O(XAH^2\ln K)$</span></p>
<p>Or also consider the relationship with the state and action space? Then it might be <span class="math-container">$O(X^2AH^2\ln K)$</span>, here I choose the highest order of each variable in both terms.</p>

CC BY-SA 4.0
2023-06-09T09:29:38.467Z
Too many parameters :)
mathworker21
CC BY-SA 4.0
2023-06-09T11:01:20.660Z
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.
white
<time-complexity><lg.learning><online-algorithms><online-learning><reinforcement-learning>
The complexity order of regret (especially in online reinforcement learning)?
white
# The complexity order of regret (especially in online reinforcement learning)?

(Asked by: username_0 on 2023-06-09)

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.

**Tags:** time-complexity, lg.learning, online-algorithms, online-learning, reinforcement-learning

> **Comments:**
> **username_1**: Too many parameters :)  
> **username_0**: 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.  

---

## 0 answers

