Cadeias de Markov e o dilema entre explorar e aproveitar em Python

O conceito em palavras simples

A IA muitas vezes precisa agir sob incerteza. Uma cadeia de Markov modela como um sistema passa de um estado para outro com probabilidades fixas, e um multi-armed bandit mostra a escolha central do aprendizado por reforço: tentar algo novo ou usar o que funcionou melhor até agora.

Preveja estados futuros com uma cadeia de Markov e equilibre exploração e aproveitamento com um bandit epsilon-greedy.

Ideias principais

Numa cadeia de Markov, o próximo estado depende só do estado atual.
As probabilidades de transição que saem de um estado sempre somam 1.
Explorar encontra opções melhores; aproveitar ganha recompensas com a melhor opção conhecida.
O epsilon controla o equilíbrio: quanto maior, mais exploração.

Quando usar?

Entender o que acontece dentro das redes neurais e das bibliotecas de IA.
Aprender a ideia antes de implementá-la nos desafios correspondentes.
Se preparar para cursos de aprendizado de máquina, entrevistas e projetos.

Veja na prática

Mude as probabilidades de transição do clima para ver onde a cadeia se estabiliza. Clique em Executar para o bandit aprender qual máquina paga mais.

Código de exemplo

Executar código →

main.py

import random

# Markov chain: tomorrow's weather depends only on today's.
transitions = {"sunny": {"sunny": 0.8, "rainy": 0.2}, "rainy": {"sunny": 0.4, "rainy": 0.6}}
dist = {"sunny": 1.0, "rainy": 0.0}
for day in range(1, 4):
    dist = {s: sum(dist[p] * transitions[p][s] for p in dist) for s in dist}
    print(f"day {day}:", {s: round(v, 3) for s, v in dist.items()})

# Epsilon-greedy bandit: usually pick the best arm so far, sometimes explore.
random.seed(1)
true_payouts = [0.3, 0.7]
counts, totals = [0, 0], [0.0, 0.0]
epsilon = 0.1
for _ in range(500):
    if random.random() < epsilon or 0 in counts:
        arm = random.randrange(2)                                  # explore
    else:
        arm = max(range(2), key=lambda a: totals[a] / counts[a])  # exploit
    reward = 1 if random.random() < true_payouts[arm] else 0
    counts[arm] += 1
    totals[arm] += reward
print("pulls per arm:", counts)
print("estimated payouts:", [round(t / c, 2) for t, c in zip(totals, counts)])

Saída esperada

day 1: {'sunny': 0.8, 'rainy': 0.2}
day 2: {'sunny': 0.72, 'rainy': 0.28}
day 3: {'sunny': 0.688, 'rainy': 0.312}
pulls per arm: [25, 475]
estimated payouts: [0.16, 0.7]

Como funciona

A cada dia, as novas probabilidades são as antigas multiplicadas pelas probabilidades de transição, então "ensolarado" cai de 1.0 para 0.688 em três dias. O bandit escolhe um braço aleatório 10% das vezes e, no resto, puxa o braço com a melhor média até ali; logo ele passa a puxar quase sempre o braço melhor e estima seu retorno em cerca de 0.7.

Altere os valores e execute o programa no compilador Python online CodeUtility sem instalar Python.

Exercícios práticos

Altere as entradas e teste casos de borda antes de usar conjuntos de dados maiores.

Mude as entradas ou os pesos e preveja a saída antes de executar.
Imprima os valores intermediários para acompanhar cada passo do cálculo.
Resolva os desafios indicados abaixo para implementar a ideia você mesmo.

Executar no IDE Python →

Pratique com um desafio

Use o conteúdo desta lição para resolver um problema real. Cada desafio roda no navegador, com testes instantâneos e uma revisão por IA.

Todos os desafios