  We give two variational formulas (qVar1) and (qVar2) for the quenched free
energy of a random walk in random potential (RWRP) when (i) the underlying walk
is directed or undirected, (ii) the environment is stationary and ergodic, and
(iii) the potential is allowed to depend on the next step of the walk which
covers random walk in random environment (RWRE). In the directed i.i.d. case,
we also give two variational formulas (aVar1) and (aVar2) for the annealed free
energy of RWRP. These four formulas are the same except that they involve
infima over different sets, and the first two are modified versions of a
previously known variational formula (qVar0) for which we provide a short
alternative proof. Then, we show that (qVar0) always has a minimizer, (aVar2)
never has any minimizers unless the RWRP is an RWRE, and (aVar1) has a
minimizer if and only if the RWRP is in the weak disorder regime. In the latter
case, the minimizer of (aVar1) is unique and it is also the unique minimizer of
(qVar1), but (qVar2) has no minimizers except for RWRE. In the case of strong
disorder, we give a sufficient condition for the nonexistence of minimizers of
(qVar1) and (qVar2) which is satisfied for the log-gamma directed polymer with
a sufficiently small parameter. We end with a conjecture which implies that
(qVar1) and (qVar2) have no minimizers under very strong disorder.
