import random
import math


def pick_action(s, values, epsilon):
    """
    Chooses an action for s based on an epsilon greedy strategy
    :param s: the state being evaluated
    :param values: The Q-values for all s-a pairs, nest Dict
    :param epsilon: the threshold for random choice, governing exploration vs. exploitation
    :return:
    """
    if random.random() < epsilon:
        return random.choice(values[s].keys())

    max_q_val = -math.inf
    max_action = None

    for action, value in values[s].items():
        if max_q_val < value:
            max_q_val = value
            max_action = action

    return max_action