I'm staying at Hotel do Papai, run by two older Lebanese (I think) men (and their fairly pretty daughters). A self contained single is 80R$ (about 27 euros), including breakfast and good wifi. It's in the center and seems to be on the low end, price wise, compared to hotels in the direct vicinity.
Driving into town, I passed a bunch of fairly shabby looking hotels in what is called Vila Cidade Nova, around Rua Pocos de Caldas. As the crow flies, this is close to downtown Rio Branco. However, with no direct access across the river, it would be a 2k, or so, walk to the central square.
I didn't confirm the price for rooms at these hotels, but considering their location and state, I think it safe to assume they would fall in the 'budget' category.