Answers.Body: <p>I assume your algorithm to loop over <span class="math-container">$K$</span> policies (or episodes), for <span class="math-container">$H$</span> steps, on each state and action pairs (where <span class="math-container">$X=|\mathcal S|$</span> and <span class="math-container">$A=|\mathcal A|$</span> denote the size of the state and action spaces; assuming them to be discrete for simplicity.)</p>
  <p>If so, and assuming an algorithm <span class="math-container">$R_K=2X^2AH \ln K\ln H + 3XA H^2 \ln K$</span> which makes such amount of steps <em>both</em> in the worst and best case (I'll clarify that later), it's computational complexity is about:
  <span class="math-container">$$\begin{align}
  O(R_K) &amp;= O(2X^2AH \ln K\ln H + 3XA H^2) \\
         &amp;= O(X^2AH \ln K\ln H + XA H^2) &amp; (1) \\ 
         &amp;= O\big(XAH \ln K (X\ln H + H)\big) &amp; (2) \\
         &amp;= O\big(n^3\ln n\ (n\ln n + n)\big) &amp; (3) \\
         &amp;= O\big(n^4\ln^2 n + n^4\ln n\big) \\
         &amp;= O(n^4\ln^2 n) &amp; (4)\\
         &amp;&lt; O(n^5) &amp; (5)
  \end{align}$$</span></p>
  <p><strong>Explaination.</strong> In line (1) I discard the constants <span class="math-container">$2$</span> and <span class="math-container">$3$</span> because they don't affect the complexity. Then, in line (2) I group by the common factor <span class="math-container">$XAH\ln K$</span>. Next in (3), I rewrite <span class="math-container">$n=XAH\ln K$</span> note that this is not mathematically exact but for the purpose of computational complexity you can assume <span class="math-container">$n$</span> to be your overall input size, i.e. the complexity of the algo <span class="math-container">$R_K$</span> is a function of <span class="math-container">$n$</span>. In line (4) the term <span class="math-container">$n^4\ln^2 n$</span> dominates <span class="math-container">$n^4\ln n$</span>, so you can remove the latter. Lastly, your final complexity is <span class="math-container">$O(n^4\ln^2 n)$</span> but if you're not sure of its scale you can further bound with a degree-five function, i.e. <span class="math-container">$n^4\ln^2 n$</span> doesn't grow as fast as <span class="math-container">$n^5$</span>.</p>
  <p>(Last point: if your algo behaves the same both in the worst <span class="math-container">$O(\cdot)$</span> and best <span class="math-container">$\Omega(\cdot)$</span> case, your <em>average complexity</em> is <span class="math-container">$\Theta(n^4\ln^2 n)$</span>.)</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-06-09T15:13:25.153Z
Answers.LastActivityDate: 2023-06-09T15:13:25.153Z
Answers.UserDisplayName: Luca Anzalone
Body: <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>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-06-09T09:21:23.533Z
Comments.Text: Do you mean the computational/algorithmic complexity to compute the regret?
Comments.UserDisplayName: Luca Anzalone
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-06-09T11:01:52.230Z
Comments.Text: 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.
Comments.UserDisplayName: white
Tags: <reinforcement-learning><machine-learning><time-complexity><online-learning><regret>
Title: The complexity order of regret (especially in online reinforcement learning)?
UserDisplayName: white
ThreadText: # 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:** reinforcement-learning, machine-learning, time-complexity, online-learning, regret
  > **Comments:**
  > **username_1**: Do you mean the computational/algorithmic complexity to compute the regret?  
  > **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.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2023-06-09. Score: 1
  
  I assume your algorithm to loop over $K$ policies (or episodes), for $H$ steps, on each state and action pairs (where $X=|\mathcal S|$ and $A=|\mathcal A|$ denote the size of the state and action spaces; assuming them to be discrete for simplicity.)
  
  If so, and assuming an algorithm $R\_K=2X^2AH \ln K\ln H + 3XA H^2 \ln K$ which makes such amount of steps *both* in the worst and best case (I'll clarify that later), it's computational complexity is about:
  $$\begin{align}
  O(R\_K) &= O(2X^2AH \ln K\ln H + 3XA H^2) \\
  &= O(X^2AH \ln K\ln H + XA H^2) & (1) \\
  &= O\big(XAH \ln K (X\ln H + H)\big) & (2) \\
  &= O\big(n^3\ln n\ (n\ln n + n)\big) & (3) \\
  &= O\big(n^4\ln^2 n + n^4\ln n\big) \\
  &= O(n^4\ln^2 n) & (4)\\
  &< O(n^5) & (5)
  \end{align}$$
  
  **Explaination.** In line (1) I discard the constants $2$ and $3$ because they don't affect the complexity. Then, in line (2) I group by the common factor $XAH\ln K$. Next in (3), I rewrite $n=XAH\ln K$ note that this is not mathematically exact but for the purpose of computational complexity you can assume $n$ to be your overall input size, i.e. the complexity of the algo $R\_K$ is a function of $n$. In line (4) the term $n^4\ln^2 n$ dominates $n^4\ln n$, so you can remove the latter. Lastly, your final complexity is $O(n^4\ln^2 n)$ but if you're not sure of its scale you can further bound with a degree-five function, i.e. $n^4\ln^2 n$ doesn't grow as fast as $n^5$.
  
  (Last point: if your algo behaves the same both in the worst $O(\cdot)$ and best $\Omega(\cdot)$ case, your *average complexity* is $\Theta(n^4\ln^2 n)$.)
  
  
  ---
  
  