-1
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ @ 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. $\endgroup$
    – DSPinfinity
    Apr 8, 2022 at 13:51
  • 1
    $\begingroup$ @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. $\endgroup$
    – Neil Slater
    Apr 8, 2022 at 15:10

Not the answer you're looking for? Browse other questions tagged .