Herself’s Artificial Intelligence

This is an algorithm where an artificial intelligence interacts with the environment, receives either positive or negative feedback and adjusts its behavior due to this reinforcement.

Reinforcement learning is usually used to solve Markov decision problems. Markov decision problems have a set of states; possible actions for each state; probabilities and rewards for each action; and a goal for the artificial intelligence to reach.

We start by setting up an environment of states. The artificial intelligence then repeatedly explores our states and will learn an optimal method of finding a path from start to goal that gains it the most rewards. Think of a game character starting on one square of a grid and trying to get to the final square. Between the start and end square are squares filled with gold and traps, like a Wupus World game board. Reinforcement learning is used in control problems for robotics, not just in games.

Learning can be supervised or unsupervised.

One popular unsupervised reinforcement learning algorithm is the Q Learning Algorithm.

Start:
Loop:
For current state select an action
Collect reward or cost
Update Q Value
Move to new state
End Loop:

Update Q Value
Q-Value += Learning_Rate ( Reward_New_State + Discount_Factor( Max_Q_New_State - Q-Value ) )

Move to new state
Use either Greedy algorithm or a Probabilistic Greedy which calculates best choices and randomly chooses one of the better choices.

This algorithm can be slow and memory intensive but has been used successfully in game problems, scheduling problems, and robotic problems.

See also:
Hidden Markov Models
Why Reinforcement Learning is Important
Reinforcement Learning (CASTrader Blog)
Wiki, Reinforcement Learning
Wiki, Q Learning

More information:
Ms. Pac-Man Plays Herself