2

I encountered the following problem as part of a quiz:

Imagine you are designing a digit recognition agent and you want to analyze the state space of this problem. Given a binary image of 28 x 28 grid of pixels where a 1 represents black color and a 0 represents white color. The agent has to determine the digit from 10 possible values, 0, 1, ..., 9. Compute the state space.

I am confused between two approaches to solve this problem.

  1. The state space consists of all possible configurations of the grid. The number of these combinations is 2^(28x28)= 2^(784). So the size of the state space is 2^(784).

  2. Because there are 10 digits and the agent must find search all combinations for each digit, the state space is 10^(2^(784)).

Is the size of the state space (2^(784) or 10^(2^(784))?

Dawood Ahmad
  • 43
  • 4

2 Answers2

2

State space in contextual bandits or reinforcement learning covers the input space to a policy or predictive model. The question also specifies a representation for this input, which is different in some ways from the meaningful space that the problem presents to you (most practical representations are larger spaces that include the whole problem plus a lot of possible values that are not relevant), but from the wording of the question, I don't think you are expected to consider that.

With that in mind, I think the question is expecting your first answer, $2^{784}$.

The larger space you consider in your second solution, I would not call the "state space". It is instead either:

  • The space of all possible input/output pairs, irrespective of correctness or usefulness to the problem. You could consider that as your search space for finding the agent's prediction function, and I think another answer explains the correct size for that, $10 \times 2^{784}$.

or:

  • The value $10^{2^{784}}$ is also meaningful, and is the space of all possible agents, that can arbitrarily choose an output in $[0,9]$ for each of the $2^{784}$ representable inputs.

I cannot rule out that the question is considering state from the perspective of something searching for an agent. In which case the other answer is correct. It is not the definition I would use, coming from a reinforcement learning or machine learning background. But it may depend on the learning materials which would be the preferred answer.

Neil Slater
  • 33,739
  • 3
  • 47
  • 66
0

It's an interesting question!

I would say, that the element of the state space is an example of observation. In your problem an observation is a pair of image and label, say ( X, y ). Image lies in space $\{0, 1\}^{28 x 28}$ and the label lies in space $\{0, 1, 2, 3, ..., 9 \}$. Therefore, you have $$ (X, y) \in \{0, 1\}^{784} \times\{0, 1, 2, 3, ..., 9\} $$ $$ |(X, y)| = 10*2^{784} $$

vl_knd
  • 496
  • 4
  • 14