Answers.Body: <blockquote>
  <p>Q1- Why is each <span class="math-container">$x_i$</span> an &quot;order-n&quot; polynomial? I think this is wrong: in my opinion, order of <span class="math-container">$x_i$</span> can be in the range [1, n*k]</p>
  </blockquote>
  <p>The text does not claim that <span class="math-container">$x_i$</span> is an &quot;order-n&quot; polynomial - the order is instead associated with the whole polynomial basis set, and <span class="math-container">$x_i$</span> is a feature of that basis. The authors are using <em>order-n</em> as the higher level descriptor of a set of terms which have <em>degree</em> up to <span class="math-container">$n$</span>.</p>
  <p>The individual terms are polynomials of the original state features of <em>degree</em> from <span class="math-container">$0$</span> to <span class="math-container">$n$</span> in each feature separately.</p>
  <blockquote>
  <p>Q2- This sentence is not clear: &quot;These
  features make up the order-n polynomial basis for dimension k, which contains
  <span class="math-container">$(n + 1)^k$</span> different features&quot;.  What does it mean &quot;for dimension k&quot;? Why specifically dimension k?</p>
  </blockquote>
  <p>The original state vector is an <span class="math-container">$\mathbb{R}^k$</span> vector. So <span class="math-container">$k$</span> refers to the original dimensionality of the state description.</p>
  <blockquote>
  <p>Q3- What is the range for index &quot;i&quot;?</p>
  </blockquote>
  <p>It is <span class="math-container">$[1, (n + 1)^k]$</span> if you are intending to have full coverage of all possible combinations of state features in degree up to <span class="math-container">$n$</span> in each feature, as described in the text.</p>
  <p>It is not the only way to create a set of derived features using polynomials, and you might just as naturally limit the total degree of all original features within a single ploynomial to <span class="math-container">$n$</span> as allow each one to vary from <span class="math-container">$0$</span> to <span class="math-container">$n$</span> in all combinations.</p>
  <p>For instance, the book gives an example with <span class="math-container">$k = 2, n = 2$</span> of <span class="math-container">$x(s) = (1, s_1, s_2, s_1s_2, s_1^2, s_2^2, s_1s_2^2, s_1^2s_2, s_1^2s_2^2)$</span>, but you could instead consider  <span class="math-container">$x(s) = (1, s_1, s_2, s_1s_2, s_1^2, s_2^2)$</span>. Which to use will depend on experimentation and results, no different from any other feature engineering.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-04-08T13:51:49.983Z
Answers.Text: @ Neil Slater,  "each order-n polynomial-basis feature $x_i$" means $x_i$ is a feature and its order is $n$. I asked a friend with math phd degree and he told me as well that the wording here is horrible.
Answers.UserDisplayName: DSPinfinity
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-04-08T15:10:33.597Z
Answers.Text: @DSPinfinity DIfferent disciplines may use terms like degree and order in subtly different ways. I would agree that the sentence is written ambiguously. My answer provides what I read as the intended meaning, or at least a pragmatic reading given the rest of the description and how you might expand a state feature vector using polynomial combinations of the original state vector.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-04-08T06:54:33.220Z
Answers.LastActivityDate: 2022-04-08T08:11:13.267Z
Answers.LastEditDate: 2022-04-08T08:11:13.267Z
Answers.UserDisplayName: Neil Slater
Body: <p>I have 3 questions for the following box from Sutton-Barto's RL book (page 211) on polynomial basis:</p>
  <p>Q1- Why is each <span class="math-container">$x_i$</span> an &quot;order-n&quot; polynomial? I think this is wrong: in my opinion, order of <span class="math-container">$x_i$</span> can be in the range [1, n*k]</p>
  <p>Q2- This sentence is not clear: &quot;These
  features make up the order-n polynomial basis for dimension k, which contains
  <span class="math-container">$(n + 1)^k$</span> different features&quot;.  What does it mean &quot;for dimension k&quot;? Why specifically dimension k?</p>
  <p>Q3- What is the range for index &quot;i&quot;?</p>
  <p><a href="https://i.sstatic.net/M8N1i.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/M8N1i.png" alt="enter image description here" /></a></p>
  
Tags: <reinforcement-learning><function-approximation>
Title: Unclear points for polynomial basis for function approximation
UserDisplayName: DSPinfinity
ThreadText: # Unclear points for polynomial basis for function approximation
  
  (Asked by: username_0 on 2022-04-07)
  
  I have 3 questions for the following box from Sutton-Barto's RL book (page 211) on polynomial basis:
  
  Q1- Why is each $x\_i$ an "order-n" polynomial? I think this is wrong: in my opinion, order of $x\_i$ can be in the range [1, n\*k]
  
  Q2- This sentence is not clear: "These
  features make up the order-n polynomial basis for dimension k, which contains
  $(n + 1)^k$ different features". What does it mean "for dimension k"? Why specifically dimension k?
  
  Q3- What is the range for index "i"?
  
  [![enter image description here](https://i.sstatic.net/M8N1i.png)](https://i.sstatic.net/M8N1i.png)
  
  **Tags:** reinforcement-learning, function-approximation
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2022-04-08. Score: 1 | Accepted answer
  
  > Q1- Why is each $x\_i$ an "order-n" polynomial? I think this is wrong: in my opinion, order of $x\_i$ can be in the range [1, n\*k]
  
  The text does not claim that $x\_i$ is an "order-n" polynomial - the order is instead associated with the whole polynomial basis set, and $x\_i$ is a feature of that basis. The authors are using *order-n* as the higher level descriptor of a set of terms which have *degree* up to $n$.
  
  The individual terms are polynomials of the original state features of *degree* from $0$ to $n$ in each feature separately.
  
  > Q2- This sentence is not clear: "These
  > features make up the order-n polynomial basis for dimension k, which contains
  > $(n + 1)^k$ different features". What does it mean "for dimension k"? Why specifically dimension k?
  
  The original state vector is an $\mathbb{R}^k$ vector. So $k$ refers to the original dimensionality of the state description.
  
  > Q3- What is the range for index "i"?
  
  It is $[1, (n + 1)^k]$ if you are intending to have full coverage of all possible combinations of state features in degree up to $n$ in each feature, as described in the text.
  
  It is not the only way to create a set of derived features using polynomials, and you might just as naturally limit the total degree of all original features within a single ploynomial to $n$ as allow each one to vary from $0$ to $n$ in all combinations.
  
  For instance, the book gives an example with $k = 2, n = 2$ of $x(s) = (1, s\_1, s\_2, s\_1s\_2, s\_1^2, s\_2^2, s\_1s\_2^2, s\_1^2s\_2, s\_1^2s\_2^2)$, but you could instead consider $x(s) = (1, s\_1, s\_2, s\_1s\_2, s\_1^2, s\_2^2)$. Which to use will depend on experimentation and results, no different from any other feature engineering.
  
  > **Comments:**
  > **username_0**: @ Neil Slater,  "each order-n polynomial-basis feature $x_i$" means $x_i$ is a feature and its order is $n$. I asked a friend with math phd degree and he told me as well that the wording here is horrible.  
  > **username_1**: @DSPinfinity DIfferent disciplines may use terms like degree and order in subtly different ways. I would agree that the sentence is written ambiguously. My answer provides what I read as the intended meaning, or at least a pragmatic reading given the rest of the description and how you might expand a state feature vector using polynomial combinations of the original state vector.  
  
  ---
  
  