How do AI's learn to act when the problem space is too big
That is a good question and many scientists around the world are asking the same. Well, first a game like Age of Empires is not considered to have a really big solution space, there are not so many things you can do. It's the same in games like Mario Bros. The problem of learning in easy games like Atari games was solve by the guys of DeepMind (here the paper), that was acquired by Google. They used an implementation of Reinforcement Learning with Deep Learning.

Going back to your question. A really big problem is how to imitate the amount of decisions a human being takes every day. Wake up, have breakfast, take a shower, leave your house... All these action need a really high level of intelligence and many actions to develop. 

There are many people working on this problem, I'm one of them. I don't know the solution but I can tell you in which way I'm looking. I follow the theories of Marvin Minsky, he is one of the fathers of AI. This book, the Emotion Machine, tells a very good view of the problem. He suggested that the way to create a machine that imitates the human behavior is not by constructing an unified compact theory of artificial intelligence. On the contrary, he argues that our brain contains resources that compete
between each other to satisfy different goals at the same moment. They called this Ways to Think.