We study tradeoffs between mistakes and oracle calls in online and transductive online learning, proving tight mistake bounds for the online setting and showing that transductive learning admits improved bounds, with further gains from randomization.