An automatic scaling system and method for reducing state space in reinforced learning for automatic scaling of a multi-tier application uses a state decision tree that is updated with new states of the multi-tier application. When a new state of the multi-tier application is received, the new state is placed in an existing node of the state decision tree only if a first attribute of the new state is same as a first attribute of any state contained in the existing node and a second attribute of the new state is sufficiently similar to a second attribute of each existing state contained in the existing node based on a similarity measurement of the second attribute of each state contained in the existing node with the second attribute of the new state.